The Library
Sketch-flip-merge : mergeable sketches for private distinct counting
Tools
Hehir, J., Ting, D. and Cormode, Graham (2023) Sketch-flip-merge : mergeable sketches for private distinct counting. In: Fortieth International Conference on Machine Learning (ICML) 2023, Hawaii , 23-29 Jul 2023. Published in: Proceedings of the 40 th International Conference on Machine Learning, 202 pp. 12846-12865. (In Press)
|
PDF
WRAP-Sketch-flip-merge-mergeable-sketches-for-private-distinct-counting-23.pdf - Accepted Version - Requires a PDF viewer. Download (681Kb) | Preview |
Official URL: https://proceedings.mlr.press/v202/hehir23a.html
Abstract
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.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Electronic data processing, Algorithms | |||||||||
Journal or Publication Title: | Proceedings of the 40 th International Conference on Machine Learning | |||||||||
Publisher: | MLR press | |||||||||
Official Date: | 23 July 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 202 | |||||||||
Page Range: | pp. 12846-12865 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | In Press | |||||||||
Access rights to Published version: | Free Access (unspecified licence, 'bronze OA') | |||||||||
Date of first compliant deposit: | 5 May 2023 | |||||||||
Date of first compliant Open Access: | 4 September 2023 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | Fortieth International Conference on Machine Learning (ICML) 2023 | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Hawaii | |||||||||
Date(s) of Event: | 23-29 Jul 2023 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year