Abstract: Given a data stream of m elements, the Distinct Elements problem is to estimate the number of distinct elements in the stream. Distinct Elements has been a subject of theoretical and empirical investigations over the past four decades resulting in space-optimal algorithms for it. However, all the current state-of-the-art algorithms are often difficult to analyze or impractical.
I will present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with a knowledge of basic probability theory.
In addition to the simplicity, the approach has significant theoretical and practical implications: our approach allowed us to resolve the open problem of (Discrete) Klee's Measure Problem in the streaming setting and build a state-of-the-art DNF counter in practice.
Bio: Kuldeep Meel holds the NUS Presidential Young Professorship in the School of Computing at the National University of Singapore (NUS). His research interests lie at the intersection of Formal Methods and Artificial Intelligence. He is a recipient of the 2022 ACP Early Career Researcher Award, the 2019 NRF Fellowship for AI and was named AI's 10 to Watch by IEEE Intelligent Systems in 2020. His research program's recent recognitions include the CACM Research Highlight Award, ACM SIGMOD Research Highlight, IJCAI-22 Early Career Spotlight, "Best Papers of CAV" (2022 and 2020) invite from FMSD journal, IJCAI-19 Sister conferences best paper award track invitation.