CVS: Fast cardinality estimation for large-scale data streams over sliding windows

详细信息    查看全文

• 作者：Jingsong Shan^a ; ^b ; ^{shanjings@hyit.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Jianxin Luo^a ; ^{ljx555@163.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Guiqiang Ni^a ; ^{networkmanage707@gmail.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Zhaofeng Wu^a ; ^{qqk20080915@163.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Weiwei Duan^a ; ^{duanweiwei@vip.163.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Data stream ; Sliding window ; Counter vector sketch ; Cardinality ; Random update
• 刊名：Neurocomputing
• 出版年：2016
• 出版时间：19 June 2016
• 年：2016
• 卷：194
• 期：Complete
• 页码：107-116
• 全文大小：2265 K

文摘

Estimating the cardinality of data streams over a sliding window is an important problem in many applications, such as network traffic monitoring, web access log analysis and database. The problem becomes more difficult in large-scale data streams when time and space complexity is taken into account. In this paper, we present a novel randomized data structure to address the problem. The significant contributions are as follows: (1) A space-efficient counter vector sketch (CVS) are proposed, which extends the well-known bitmap sketch to sliding window settings. (2) Based on the CVS, a random update mechanism is introduced, whereby a small fixed number of entries are randomly chosen from CVS in a step and then updated. This means that the update procedure just costs constant time. (3) Furthermore, estimating cardinality by CVS just needs one-pass scan of the data. (4) Finally, a theoretical analysis is given to show the accuracy of CVS-based estimators. Our comprehensive experiments confirm that the CVS-based schema attains high accuracy, and demonstate its time efficiency in comparison with the Timestamp Vector (TSV) and the auxiliary indexing method.