Estimating the number of distinct elements (F0) in a data stream is a fundamental
problem in streaming computation. However an exact solution in the single-pass,
memory-limited model requires, in the worst case, Ω(N ) space, where N is the size of
the element domain, which is infeasible for real-world streams. This thesis examines
randomized (ϵ, δ)-approximation algorithms that, through randomness and hash
functions, achieve accurate estimates of F0 using substantially less, polylogarithmic
space. We present and prove the correctness of four algorithms in detail: the
CVM algorithm, Knuth’s optimization of CVM, the Tidemark algorithm, and the
BJKST algorithm. We then validate these theoretical results experimentally, all four
algorithms are implemented and evaluated on eight standardized benchmark data
streams across varying stream lengths and space budgets. The results confirm that
the accuracy of the CVM algorithm, Knuth’s optimization of CVM, and the BJKST
algorithm remains stable regardless of stream length, while the Tidemark algorithm,
lacking an (ϵ, δ)-guarantee, cannot go below a structural accuracy floor arising from
its estimate being discretized to powers of 2.
|
