Distinct Elements in Streams and the Klee's Measure Problem

Add to your list(s) Download to your calendar using vCal

• Sourav Chakraborty (ISI)
• Tuesday 18 March 2025, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

The distinct elements problem in streaming algorithms refers to estimating the number of unique elements in a data stream while using limited memory. A generalization of this problem is Klee’s Measure Problem, where the goal is to estimate the size of the union of sets when the sets arrive in a data stream, all while using limited memory and having restricted access to the sets.

While the distinct elements problem is well-studied in streaming algorithms, with tight bounds already established, Klee’s Measure Problem has remained a major open problem in the field for many years.

We will present the first-ever efficient streaming algorithm (from PODS ‘21) for Klee’s Measure Problem. This algorithm also provides a remarkably simple streaming solution for the distinct elements estimation problem, which even caught the attention of Donald E. Knuth (https://www-cs-faculty.stanford.edu/~knuth/papers/cvm-note.pdf).

This talk 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 Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations. (jointly with Mridul Nandi, Arijit Ghosh and Soumit Pal) APPROX 2024

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.