Estimating the Size of Unions of Sets in Streaming Models
Abstract:
Feeling tired of complicated theorems with complicated proofs? Fret not; this week will be different: A simple theorem with a simpler proof for a general problem. I will make a case for our upcoming PODS-21 paper to be the simplest paper ever accepted at PODS.
I will discuss estimation of the size of the union of Delphic sets wherein each set is implicitly (and succinctly) represented, and comes in a streaming fashion. The notion of Delphic sets captures the class of streaming problems where membership, sampling, and counting calls are efficient. The notion of Delphic sets captures several well-known problems, such as Klee's measure, distinct elements, and model counting of DNF formulas.
The primary contribution of our work is a simple, elegant, and efficient sampling-based algorithm for the estimation of the union in the streaming setting. Our algorithm has the worst case space complexity and update time, which is logarithmic in the size of the universe and stream size. Consequently, our algorithm provides the first algorithm with a linear dependence on $d$ for Klee's measure problem in streaming setting for d>1, thereby settling the open problem of Woodruff and Tirthpura (PODS-12). The Klee's measure problem corresponds to computation of volume of multi-dimension axis-aligned rectangles, i.e., every d-dimension axis-aligned rectangle can be defined as [a_1,b_1] x [a_2,b_2] x ... x [a_d, b_d].
(Joint work with N.V. Vinodchandran (r) Sourav Chakraborty)
Biodata:
Kuldeep Meel is Sung Kah Kay Assistant Professor in the Computer Science Department of School of Computing at National University of Singapore. He is an affiliate at Institute of Data Science. He is a receipient of 2019 NRF Fellowship for AI, and was named AI's 10 to Watch by IEEE Intelligent Systems in 2020.
His research interests are at the intersection of formal methods and artificial intelligence. His research program's long-term vision is to advance automated reasoning techniques to enable computing to deal with increasingly uncertain real-world environments.