Abstract
Cardinality sketches are compact data structures used to represent sets or vectors, and they are widely deployed in practice. These sketches are space-efficient, typically requiring only logarithmic storage in the input size. Importantly, they are composable, meaning that the sketch of a union of sets can be computed from the sketches of the individual sets. They enable approximate computation of cardinality (i.e., the number of nonzero entries). Statistical guarantees ensure accurate answers to a number of queries that is exponential in the sketch size k when the queries are non-adaptive. However, these guarantees degrade significantly, to only quadratic in k, when the queries are adaptive.
In this talk, we demonstrate that this quadratic vulnerability to adaptive queries is inherent for broad classes of cardinality sketches, based on the combinatorial properties of composable mappings.
Joint work with: Sara Ahmadian, Jelani Nelson, Tamás Sarlós, Mihor Singhal, and Uri Stemmer