Streaming Algorithms for Robust Distinct Elements

Summary: Estimates the number of distinct entities in streams under a noisy model where items may map to the same entity. Introduces bucket sampling for Euclidean spaces, extends to metric spaces via LSH, and shows resilience to small ambiguity with practical validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5168
Venue: SIGMOD
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,034 | 17.44%
DOI: 10.1145/2882903.2882915

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Di Chen (Hong Kong University of Science and Technology)
2. Qin Zhang (Indiana University)

BibTeX Citation

@inproceedings{chen_sigmod16,
        title = {{Streaming Algorithms for Robust Distinct Elements}},
        author = {Chen, Di and Zhang, Qin},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882915},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882915},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,156	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	5.093636e-05
10,651	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	5.093636e-05
11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.0024089429
254	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00023199211
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
1,783	Data Fusion – Resolving Data Conflicts for Integration	2009	VLDB	9.772895e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,533	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD
2	5,385	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB
3	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
4	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
5	4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS
6	482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS
7	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
8	12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
9	11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
10	10,651	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS