An Optimal Algorithm for the Distinct Elements Problem

Summary: First algorithm achieving information-theoretically optimal space O(ε^-2 + log n) bits for (1±ε)-approximate distinct elements in data streams, closing decades of work. Also attains worst-case O(1) update and reporting time and extends to Hamming-norm estimation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h68fa01eaea4d21b2
Venue: PODS
Year: 2010
Pagerank: 0.00017347522
Overall Rank: 495 | 96.69%
DOI: 10.1145/1807085.1807094

Incoming Non-self Citations Over Time

Authors

1. Daniel M. Kane (Harvard University)
2. Jelani Nelson (Massachusetts Institute of Technology)
3. David P. Woodruff (IBM)

BibTeX Citation

@inproceedings{kane_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{An Optimal Algorithm for the Distinct Elements Problem}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807094},
        doi = {10.1145/1807085.1807094},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kane, Daniel M. and Nelson, Jelani and Woodruff, David P.},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
452	Mergeable Summaries	2012	PODS	0.00018032092
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013752994
1,153	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011763855
2,789	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	7.996482e-05
3,064	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.6775964e-05
3,871	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS	6.9414117e-05
4,329	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.64569e-05
4,390	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.6110397e-05
5,119	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	6.2541554e-05
5,399	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1336701e-05
5,761	Data Streams with Bounded Deletions	2018	PODS	5.9847577e-05
6,136	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.8578818e-05
6,138	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.8575652e-05
7,096	Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond	2023	PODS	5.5853839e-05
7,387	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5212177e-05
7,497	On the Feasibility of Forgetting in Data Streams	2024	PODS	5.4960465e-05
7,869	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	5.4206136e-05
8,110	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS	5.3739121e-05
8,458	Streaming Algorithms for Measuring H-Impact	2017	PODS	5.3148581e-05
10,457	On Sketching Trimmed Statistics	2026	PODS	4.9605343e-05
10,475	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS	4.9605343e-05
10,598	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD	4.9605343e-05
11,164	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.9605343e-05
11,742	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	4.9605343e-05
11,743	Applications of Sketching and Pathways to Impact	2023	PODS	4.9605343e-05
11,887	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	2022	PODS	4.9605343e-05
11,988	Model Counting meets F0 Estimation	2021	PODS	4.9605343e-05
11,997	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	4.9605343e-05
12,243	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9605343e-05
12,246	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9605343e-05
12,248	Reconciling Graphs and Sets of Sets	2018	PODS	4.9605343e-05
12,378	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023948467
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
337	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020593498
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018277436
660	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.00015022694
711	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014589586
2,245	Multi-Dimensional Clustering: A New Data Layout Scheme in DB2	2003	SIGMOD	8.7628897e-05
3,219	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.50928e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,284	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD
2	13,007	A Simple and Efficient Estimation Method for Stream Expression Cardinalities	2007	VLDB
3	6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
4	11,529	Streaming Algorithms with Few State Changes	2024	PODS
5	911	Finding Frequent Items in Data Streams	2008	VLDB
6	3,219	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB
7	13,062	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
8	12,246	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
9	11,995	Frequent Elements with Witnesses in Data Streams	2021	PODS
10	12,378	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD