An optimal algorithm for the distinct elements problem

By Daniel M. Kane, Jelani Nelson, David P. Woodruff. 2010

376 citations recorded by the source corpus.

We give the first optimal algorithm for estimating the number of distinct elements in a data stream, closing a long line of theoretical research on this problem begun by Flajolet and Martin in their seminal paper in FOCS 1983. This problem has applications to query optimization, Internet routing, network topology, and data mining. For a stream of indices in {1,...,n}, our algorithm computes a (1 ± ε)-approximation using an optimal O(1/ε-2 + log(n)) bits of space with 2/3 success probability, where 0<ε<1 is given. This probability can be amplified by independent repetition. Furthermore, our algorithm processes each stream update in O(1) worst-case time, and can report an estimate at any point midstream in O(1) worst-case time, thus settling both the space and time complexities simultaneously. We also give an algorithm to estimate the Hamming norm of a stream, a generalization of the number of distinct elements, which is useful in data cleaning, packet tracing, and database auditing. Our algorithm uses nearly optimal space, and has optimal O(1) update and reporting times.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “Beside its use in database management systems, it is a well-studied problem in sketching, streaming, and communication complexity (e.g., [30, 9] and the references therein).”
Pan-private algorithms via statistics on sketches (2011, background): “[11] show that if f is picked from an r-wise independent family, where r = Ω(log(k/β)/ log log(k/β)), then the lower bound on the”
An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (2018, methodology): “There are many streaming algorithms (e.g., Hyperloglog) [20, 28] which achieve (1 ± α ) - approximation factor on the number of distinct elements with a space requirement of polylog ( n ) .”
A CLT and tight lower bounds for estimating entropy (2010, background): “We explicitly exhibit such a family of pairs of distributions D,D′ via a Laguerre polynomial construction that may be of independent interest.”
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs (2011, background): “Additionally, there has been much work on estimating the support size (and the general problem of estimating frequency moments) and estimating the entropy in the setting of streaming, in which one has access to very little memory and can perform only a single pass over the data [2, 3, 10, 14, 25, 26”
Tight bounds for distributed functional monitoring (2011, neutral): “By Fact1 and Lemma1 in [39] we haveE[R] = l ( 1− (1− 1/l)N ) andVar[R] < 4N2/l.”
Efficient Differentially Private F0 Linear Sketching (2020, methodology): “Sampling-based methods [22] can in many cases be improved by using algorithms designed with data streams in mind [25].”
HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm (2013, methodology): “There are two popular models to describe and analyse cardinality estimation algorithms: Firstly, the data streaming (ε, δ)-model [10, 11] analyses the necessary space to get a (1 ± ε)-approximation with a fixed success probability of δ, for example δ = 2/3, for cardinalities in {1, .”
Graph sketches: sparsification, spanners, and subgraphs (2012, background): “, finding heavy hitters and quantiles [10, 13]; estimating norms and support sizes [32, 33]; and constructing histograms and low-dimensional approximations [11, 26].”
The Power of Linear Estimators (2011, background): “There has been much work on estimating the support size (and the general problem of estimating frequency moments) and estimating the entropy in the setting of streaming, in which one has access to very little memory and can perform only a single pass over the data [1], [2], [12], [17], [18], [19].”