Timezone: »
Data sketching is a critical tool for distinct counting, enabling multisets to be represented by compact summaries that admit fast cardinality estimates. Because sketches may be merged to summarize multiset unions, they are a basic building block in data warehouses. Although many practical sketches for cardinality estimation exist, none provide privacy when merging. We propose the first practical cardinality sketches that are simultaneously mergeable, differentially private (DP), and have low empirical errors. These introduce a novel randomized algorithm for performing logical operations on noisy bits, a tight privacy analysis, and provably optimal estimation. Our sketches dramatically outperform existing theoretical solutions in simulations and on real-world data.
Author Information
Jonathan Hehir (Pennsylvania State University)
Daniel Ting (Meta)
Graham Cormode (University of Warwick)
Related Events (a corresponding poster, oral, or spotlight)
-
2023 Poster: Sketch-Flip-Merge: Mergeable Sketches for Private Distinct Counting »
Thu. Jul 27th 12:00 -- 01:30 AM Room Exhibit Hall 1 #529
More from the Same Authors
-
2021 : The Shape of Edge Differential Privacy »
Siddharth Vishwanath · Jonathan Hehir -
2021 : Consistent Spectral Clustering of Network Block Models under Local Differential Privacy »
Jonathan Hehir · Aleksandra Slavković · Xiaoyue Niu -
2023 : Federated Experiment Design under Distributed Differential Privacy »
Wei-Ning Chen · Graham Cormode · Akash Bharadwaj · Peter Romov · Ayfer Ozgur -
2018 Poster: Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms »
Charlie Dickens · Graham Cormode · David Woodruff -
2018 Oral: Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms »
Charlie Dickens · Graham Cormode · David Woodruff