• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Distinct Elements in Streams: An Algorithm for the (Text) Book.
Sourav Chakraborty ⓡ N. V. Vinodchandran ⓡ Kuldeep S. Meel.
In Proceedings of European Symposium of Algorithms (ESA), August 2022.
Highlighted in Donald Knuth's note on the paper
Given a data stream of m elements, the Distinct Elements problem is to estimate the number of distinct elements in a stream. 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.
@inproceedings{CVM22,
title={Distinct Elements in Streams: An Algorithm for the (Text) Book},
author={Chakraborty, Sourav and Vinodchandran, N. V. and Meel, Kuldeep S.},
nameorder={random},
bib2html_pubtype={Refereed Conference},
year={2022},
month=aug,
booktitle=ESA,
bib2html_rescat={Data Streams},
abstract={
Given a data stream of m elements, the Distinct Elements problem is to
estimate the number of distinct elements in a stream.
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.
},
note={Highlighted in Donald Knuth's note on the paper},
bib2html_dl_pdf={../Papers/esa22.pdf},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Thu Apr 30, 2026 09:22:03