Paper Info
Title
Erasable Virtual HyperLogLog for Approximating Cumulative Distribution over Data Streams
Abstract
Many real-world datasets are given in the stream of entity-identifier pairs, and measuring data distribution on these datasets is fundamental for applications such as privacy protection. In this paper, we study the problem of computing the cumulative distribution for different cardinalities (i.e., the number of distinct entities owning the same identifier). However, previous sketch-based methods cost large memory space especially when there are a large number of identifiers, and sampling-based methods require much time for cardinality estimation. A recent work KHyperLogLog combines both sketch and sampling methods but it is wasteful to separately build a HyperLogLog sketch of large size for identifiers with small cardinalities. To address these challenges, we propose a memory-efficient method EV-HLL, which designs a shared structure to store all sampled identifiers and their entities and utilizes additional sketches to track value updates during the sampling procedure. Meanwhile, EV-HLL provides real-time unbiased estimations according to value changes whenever a new entity-identifier pair arrives. We evaluate the performance of EV-HLL and other state-of-the-arts on real-world available datasets. Experimental results demonstrate that comparing to other methods, EV-HLL effectively reduces their memory usage with the same estimation accuracy and has higher accuracy with the same memory usage.
Year
DOI
Venue
2022
10.1109/TKDE.2021.3052938
IEEE Transactions on Knowledge and Data Engineering
Keywords
DocType
Volume
Erasable virtual HyperLogLog,data distribution estimation,data streams
Journal
34
Issue
ISSN
Citations 
11
1041-4347
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Peng Jia18723.41
Ping-Hui Wang223633.39
Junzhou Zhao310418.36
Jing Tao46416.92
Ye Yuan511724.40
X. Guan61169137.97