Fine-grained probability counting for cardinality estimation of data streams
Fine-grained probability counting for cardinality estimation of data streams
复制标题
用于数据流基数估计的细粒度概率计数
DOI：
10.1007/s11280-018-0583-0
复制
发表时间：
2018-05
影响因子：
3.7
通讯作者：
Li Xiaoming
中科院分区：
文献类型：
--
作者：
Wang Lun;Yang Tong;Wang Hao;Jiang Jie;Cai Zekun;Cui Bin;Li Xiaoming
在许多网络应用程序（例如流量测量，异常检测等）中，估计不同流量的数量（也称为基数）是一个重要的问题。挑战是，应以线路速度和小型来实现高精度
Estimating the number of distinct flows, also called thecardinality, is an important issue in many network applications, such as traffic measurement, anomaly detection, etc. The challenge is that high accuracy should be achieved with line speed and small auxiliary memory. Flajolet-Martin algorithm, LogLog algorithm, and HyperLogLog algorithm form a line of work in this area with improving performance. In this paper, we propose refined versions of these algorithms to achieve higher accuracy. The key observations are (1) the “leftmost” hash functions used by these algorithms can be generalized to reach higher accuracy, (2) the amendment coefficient can be highly biased in some certain streams or datasets so dynamically setting the amendment coefficient instead of using the one derived in pure math can lead to much better accuracy. Experimental results show great improvement of accuracy and stability of the refined versions over original algorithms.
登录
查看更多内容
DOI：
10.1109/icdmw.2010.18
发表时间：
2010-03
期刊：
2010 IEEE International Conference on Data Mining Workshops
影响因子：
--
作者：
Yousra Chabchoub;G. Hébrail
通讯作者：
Yousra Chabchoub;G. Hébrail
DOI：
10.1109/icde.2016.7498309
发表时间：
2016-05
期刊：
2016 IEEE 32nd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Jialong Han;Kai Zheng;Aixin Sun;Shuo Shang;Ji-Rong Wen
通讯作者：
Jialong Han;Kai Zheng;Aixin Sun;Shuo Shang;Ji-Rong Wen
影响因子：
--
作者：
Steve Rotenberg
通讯作者：
Steve Rotenberg
影响因子：
1.1
作者：
FLAJOLET, P;MARTIN, GN
通讯作者：
MARTIN, GN
影响因子：
2.8
作者：
Estan, C;Varghese, G
通讯作者：
Varghese, G