2023/02/04 by Jonathan Hehir, Daniel Shu Wei Ting, Hehir, Jonathan +3 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Computation (stat.CO) #Cryptography and Security (cs.CR) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2302.02056
openalex publication_date 2023/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.