2 ms·
Distinct Elements in Streams: An Algorithm for the (Text) Book∗ [pdf]
- Bluestein 3y ago"""Given a data stream A = ⟨a1, a2, . . . , am⟩ of m elements where each ai ∈ [n], the Distinct Elements problem is to estimate the number of distinct elements in A. 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 pro"""
- yorwba 3y agoOngoing discussion on Quanta article about this paper: https://news.ycombinator.com/item?id=40379175 https://news.ycombinator.com/item?id=40379175