DBScholar

Back to papers

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.00017379171
Overall Rank
494 | 96.69%
DOI
10.1145/1807085.1807094

Incoming Non-self Citations Over Time

Authors

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
456 Mergeable Summaries 2012 PODS 0.00017904764
805 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.00013788161
1,170 Graph Sketches: Sparsification, Spanners, and Subgraphs 2012 PODS 0.00011720594
2,852 All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis 2014 PODS 7.9377182e-05
3,054 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.7030675e-05
3,859 Is Min-Wise Hashing Optimal for Summarizing Set Intersection? 2014 PODS 6.9644179e-05
4,330 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.6564176e-05
4,383 A Framework for Adversarially Robust Streaming Algorithms 2020 PODS 6.6234423e-05
5,096 Persistent Bloom Filter: Membership Testing for the Entire History 2018 SIGMOD 6.2747628e-05
5,379 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 6.1540191e-05
5,780 Data Streams with Bounded Deletions 2018 PODS 5.9949139e-05
6,122 The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 2015 PODS 5.8773159e-05
6,124 Approximate Distinct Counts for Billions of Datasets 2019 SIGMOD 5.8769926e-05
7,076 Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond 2023 PODS 5.6039139e-05
7,368 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5392867e-05
7,478 On the Feasibility of Forgetting in Data Streams 2024 PODS 5.5142801e-05
7,853 Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model 2019 PODS 5.4385028e-05
8,092 Subspace Exploration: Bounds on Projected Frequency Estimation 2021 PODS 5.3917406e-05
8,442 Streaming Algorithms for Measuring H-Impact 2017 PODS 5.3324907e-05
10,391 On Sketching Trimmed Statistics 2026 PODS 4.9769913e-05
10,409 Representation Obliviousness and Pseudodeterminism in Streaming Algorithms 2026 PODS 4.9769913e-05
10,532 A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables 2026 SIGMOD 4.9769913e-05
11,103 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 4.9769913e-05
11,696 Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation 2023 PODS 4.9769913e-05
11,697 Applications of Sketching and Pathways to Impact 2023 PODS 4.9769913e-05
11,843 Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size 2022 PODS 4.9769913e-05
11,944 Model Counting meets F0 Estimation 2021 PODS 4.9769913e-05
11,953 Estimating the Size of Union of Sets in Streaming Models 2021 PODS 4.9769913e-05
12,200 Distributed Statistical Estimation of Matrix Products with Applications 2018 PODS 4.9769913e-05
12,203 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS 4.9769913e-05
12,205 Reconciling Graphs and Sets of Sets 2018 PODS 4.9769913e-05
12,335 Streaming Algorithms for Robust Distinct Elements 2016 SIGMOD 4.9769913e-05
Previous Page 1 / 1 Next

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.0023943337
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022713652
335 The Aqua Approximate Query Answering System 1999 SIGMOD 0.000206533
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.0001831946
656 Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies 1996 VLDB 0.0001506436
707 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014633741
2,234 Multi-Dimensional Clustering: A New Data Layout Scheme in DB2 2003 SIGMOD 8.7892036e-05
3,212 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5324957e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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