# Distinct Elements in Streams: An Algorithm for the (Text) Book

arXiv: https://arxiv.org/abs/2301.10191 · HTML: https://mlsanity.com/paper/2301.10191/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2023.

## Built on by (most cited first, 1 of 1)

- [Estimating Coverage in Streams via a Modified CVM Method](https://mlsanity.com/paper/2504.04567/) (2025)

## Abstract (arXiv)

Given a data stream A = langle a1, a2, ldots, am rangle 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 proof are accessible to undergraduates with the knowledge of basic probability theory.