Distinct Elements in Streams: An Algorithm for the (Text) Book
arXiv:2301.10191 · doi:10.4230/LIPIcs.ESA.2022.34
Abstract
Given a data stream of elements where each , the Distinct Elements problem is to estimate the number of distinct elements in .Distinct Elements has been a subject of theoretical and empirical investigations over the past four decades resulting in space optimal algorithms for it.All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory.
The version of the paper, as published in ESA-22, contained an error in the proof of Claim 4. The current revised version fixes the error as well as several other errors pointed by Donald E. Knuth. The main theorem and algorithm remain unchanged. The authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by \textcircled{r}