Range-efficient computation of F0 over massive data streams
A. Pavan, Srikanta Tirthapura · 2005
Efficient one-pass computation of F 0, the number of distinct elements in a data stream, is a fundamental problem arising in various contexts in databasesand networking.We consider the problem of efficiently estimating F0 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 F0, with the following time complexity (n is the size of the universe of the items): (1)The amortized processing time per interval is O(log 1 log n � ). (2)The time toanswer a queryfor F0 is O(log 1/δ). The workspaceused is O( 1