Sliding HyperLogLog: Estimating Cardinality in a Data Stream over a Sliding Window
Sliding HyperLogLog: Estimating Cardinality in a Data Stream over a Sliding Window
复制标题
DOI：
10.1109/icdmw.2010.18
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Yousra Chabchoub;G. Hébrail
中科院分区：
文献类型：
--
作者：
Yousra Chabchoub;G. Hébrail
本文提出了一种估计数据流中活动流数的新算法。该算法通过增加滑动窗口机制，将Flajolet等人的HyperLogLog算法应用于数据流处理。它的优点是可以在任何时候估计在滑动窗口长度限定的任何持续时间内看到的流量数量。该估计非常准确，标准误差约为1.04\sqrt(m)（与HyperLogLog算法相同），其中m是所需内存中的寄存器数。由于新算法回答更灵活的查询，与HyperLogLog算法相比，它需要额外的内存存储。证明了所需的总内存最多等于5mln（n/m）字节，其中n为滑动窗口中流的实数。例如，对于只有35kB的内存，对于数百万流的数据流可以实现约3%的标准误差。理论结果在真实流量和合成流量上都得到了验证。
In this paper, a new algorithm estimating the number of active flows in a data stream is proposed. This algorithm adapts the HyperLogLog algorithm of Flajolet et al. to data stream processing by adding a sliding window mechanism. It has the advantage to estimate at any time the number of flows seen over any duration bounded by the length of the sliding window. The estimate is very accurate with a standard error of about 1.04\sqrt(m)(the same as in HyperLogLog algorithm), where m is the number of registers in the required memory. As the new algorithm answers more flexible queries, it needs additional memory storage compared to HyperLogLog algorithm. It is proved that the total required memory is at most equal to 5mln(n/m) bytes, where n is the real number of flows in the sliding window. For instance, with a memory of only 35kB, a standard error of about 3% can be achieved for a data stream of several million flows. Theoretical results are validated on both real and synthetic traffic.