Alladi Ramakrishnan Hall

Distinct Elements in Streams and the Klee's Measure Problem

Sourav Chakraborty

ISI Kolkata

We will present a very simple streaming algorithm on $F_0$ estimation
that also caught the eye of Donald E. Knuth. This simple algorithm comes out of the first ever "efficient" streaming algorithm (from PODS 21) for the Klee's Measure problem, which was a big open problem in the world of streaming for many years.

This work is based on joint works with N. V. Vinodchandran, and Kuldeep S. Meel across multiple articles, notable the following:

* Estimating the Size of Union of Sets in Streaming Models. PODS 2021

* Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size. PODS 2022

* Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022