一种基于近似零误差的概率测量数据结构Sketch的网络流量测量方法和系统

摘要

本发明涉及一种基于近似零误差的概率测量数据结构Sketch的网络流量测量方法和系统。该方法设立用于存储小流信息的CM‑Sketch数据结构和用于存储标号的数据结构；在网络流量测量过程中更新表项时，首先更新CM‑Sketch，然后基于对CM‑Sketch的观察来对存储标号的数据结构进行更新。在插入一条新的流的信息时，同时在设计的用于存储标号的数据结构中保存其标号信息以及时间戳；而在需要复原流量信息时，可根据该数据结构中存储的标号，求解方程组，得到精确的流量信息。本发明在未使得算法时间复杂度有较明显提升的前提下，解决了Elastic Sketch针对小流信息查询准确性不足的缺陷，并且能够支持瞬时查询。