Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries

Edith Cohen, Mihir Singhal, Uri Stemmer
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:11185-11199, 2025.

Abstract

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 adaptively chosen queries, breaking down after approximately $\tilde{O}(k^2)$ 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 exponential number of adaptive queries, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries sharing the same element, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-cohen25c, title = {Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries}, author = {Cohen, Edith and Singhal, Mihir and Stemmer, Uri}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {11185--11199}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/cohen25c/cohen25c.pdf}, url = {https://proceedings.mlr.press/v267/cohen25c.html}, abstract = {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 adaptively chosen queries, breaking down after approximately $\tilde{O}(k^2)$ 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 exponential number of adaptive queries, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries sharing the same element, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.} }
Endnote
%0 Conference Paper %T Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries %A Edith Cohen %A Mihir Singhal %A Uri Stemmer %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-cohen25c %I PMLR %P 11185--11199 %U https://proceedings.mlr.press/v267/cohen25c.html %V 267 %X 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 adaptively chosen queries, breaking down after approximately $\tilde{O}(k^2)$ 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 exponential number of adaptive queries, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries sharing the same element, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.
APA
Cohen, E., Singhal, M. & Stemmer, U.. (2025). Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:11185-11199 Available from https://proceedings.mlr.press/v267/cohen25c.html.

Related Material