Campus Units
Computer Science, Electrical and Computer Engineering
Document Type
Article
Publication Date
5-2007
Journal or Book Title
SIAM Journal on Computing
Volume
37
Issue
2
First Page
359
Last Page
379
DOI
10.1137/050643672
Abstract
Efficient one‐pass estimation of $F_0$, the number of distinct elements in a data stream, is a fundamental problem arising in various contexts in databases and networking. We consider range‐efficient estimation of $F_0$: estimation of the number of distinct elements in a data stream where each element of the stream is not just a single integer but an interval of integers. We present a randomized algorithm which yields an (ε, δ)‐approximation of $F_0$, with the following time and space complexities (n is the size of the universe of the items): (1) The amortized processing time per interval is $O(\log{\frac{1}{\delta}}\log \frac{n}{\epsilon})$. (2) The workspace used is $O(\frac{1}{\epsilon^2}\log{\frac{1}{\delta}}\log n)$ bits. Our algorithm improves upon a previous algorithm by Bar‐Yossef, Kumar and Sivakumar [Proceedings of the $13$th ACM–SIAM Symposium on Discrete Algorithms (SODA), 2002, pp. 623–632], which requires $O(\frac{1}{\epsilon^5} \log{\frac{1}{\delta}}\log^5 n)$ processing time per item. This algorithm can also be used to compute the max‐dominance norm of a stream of multiple signals and significantly improves upon the previous best time and space bounds by Cormode and Muthukrishnan [Proceedings of the $11$th European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 2938, Springer, Berlin, 2003, pp. 148–160]. This algorithm also provides an efficient solution to the distinct summation problem, which arises during data aggregation in sensor networks [Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, ACM Press, New York, 2004, pp. 250–262, Proceedings of the $20$th International Conference on Data Engineering (ICDE), 2004, pp. 449–460].
Copyright Owner
Society for Industrial and Applied Mathematics
Copyright Date
2007
Language
en
File Format
application/pdf
Recommended Citation
Pavan, A. and Tirthapura, Srikanta, "Range‐Efficient Counting of Distinct Elements in a Massive Data Stream" (2007). Electrical and Computer Engineering Publications. 91.
https://lib.dr.iastate.edu/ece_pubs/91
Comments
This article is from SIAM Journal on Computing 37 (2007): 359, doi: 10.1137/050643672. Posted with permission.