#### 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 Computing37 (2007): 359, doi: 10.1137/050643672. Posted with permission.