Range-efficient computation of F0 over massive data streams

Efficient one-pass computation of F₀, the number of distinct elements in a data stream, is a fundamental problem arising in various contexts in databases and networking. We consider the problem of efficiently estimating F₀ of a data stream where each element of the stream is an interval of integers. We present a randomized algorithm which gives an (ε, δ) approximation of F₀, with the following time complexity (n is the size of the universe of the items): (1) the amortized processing time per interval is O(log1/δ log n/ε). (2) The time to answer a query for F₀ is O(log1/δ). The workspace used is O(1/ε²log1/δlogn) bits. Our algorithm improves upon a previous algorithm by Bar-Yossef Kumar and Sivakumar (2002), which requires O(1/ε⁵log1/δlog⁵n) processing time per item. Our algorithm can be used to compute the max-dominance norm of a stream of multiple signals, and significantly improves upon the current best bounds due to Cormode and Muthukrishnan (2003). This also provides efficient and novel solutions for data aggregation problems in sensor networks studied by Nath and Gibbons (2004) and Considine et. al. (2004).