•
Classified by Research Topic •
Sorted by Date •
Classified by Publication Type •

## Distinct Elements in Streams: An Algorithm for the (Text) Book

** 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.

### Download

[PDF]

### 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.

### BibTeX

@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