• 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.
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. },
bib2html_dl_pdf={../Papers/esa22.pdf},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51