2025/02/08 by Edith Cohen, Cohen, Edith, Mihir Singhal +3
Computer Science · #Advanced Database Systems and Queries #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2502.05723
openalex publication_date 2025/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and computational costs. However, recent research has shown that these sketches can fail under \em adaptively chosen queries, breaking down after approximately O(k2) queries, where k is the sketch size. In this work, we overcome this quadratic barrier by designing robust estimators with fine-grained guarantees. Specifically, our constructions can handle an \em exponential number of adaptive queries, provided that each element participates in at most O(k2) queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries \em sharing the same element, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.