Given @math distributed data streams @math , we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over @math . We identify a broad class of algorithms for solving this problem, and show that the estimators output by any algorithm in this class are perfectly unbiased and satisfy strong variance bounds. Our analysis unifies and generalizes a variety of earlier results in the literature. To demonstrate its generality, we describe several novel sampling algorithms in our class, and show that they achieve a novel tradeoff between accuracy, space usage, update speed, and applicability.
@cite_13: It is possible to use a small counter to keep approximate counts of large numbers. The resulting expected error can be rather precisely controlled. An example is given in which 8-bit counters (bytes) are used to keep track of as many as 130,000 events with a relative error which is substantially independent of the number n of events. This relative error can be expected to be 24 percent or less 95 percent of the time (i.e. s = n 8). The techniques could be used to advantage in multichannel counting hardware or software used for the monitoring of experiments or processes.
This paper's Alpha Algorithm'' is inspired by the elegant Approximate Counting method of Morris @cite_13 , that has previously been applied to the estimation of the frequency moments @math , for @math . By contrast, our task is to estimate @math . The Alpha Algorithm is able to do this because its Approximate Counting process is tightly interleaved with another process that removes duplicates from the input stream while maintaining a small memory footprint by using feedback from the approximate counter.