@COMMENT This file was generated by bib2html.pl version 0.94
@COMMENT written by Patrick Riley
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@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},
}