Scalable contribution bounding to achieve privacy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916873376890880 |
|---|---|
| author | Cohen-Addad, Vincent Epasto, Alessandro Lee, Jason Zadimoghaddam, Morteza |
| author_facet | Cohen-Addad, Vincent Epasto, Alessandro Lee, Jason Zadimoghaddam, Morteza |
| contents | In modern datasets, where single records can have multiple owners, enforcing user-level differential privacy requires capping each user's total contribution. This "contribution bounding" becomes a significant combinatorial challenge. Existing sequential algorithms for this task are computationally intensive and do not scale to the massive datasets prevalent today. To address this scalability bottleneck, we propose a novel and efficient distributed algorithm. Our approach models the complex ownership structure as a hypergraph, where users are vertices and records are hyperedges. The algorithm proceeds in rounds, allowing users to propose records in parallel. A record is added to the final dataset only if all its owners unanimously agree, thereby ensuring that no user's predefined contribution limit is violated. This method aims to maximize the size of the resulting dataset for high utility while providing a practical, scalable solution for implementing user-level privacy in large, real-world systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23432 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scalable contribution bounding to achieve privacy Cohen-Addad, Vincent Epasto, Alessandro Lee, Jason Zadimoghaddam, Morteza Data Structures and Algorithms Cryptography and Security Distributed, Parallel, and Cluster Computing In modern datasets, where single records can have multiple owners, enforcing user-level differential privacy requires capping each user's total contribution. This "contribution bounding" becomes a significant combinatorial challenge. Existing sequential algorithms for this task are computationally intensive and do not scale to the massive datasets prevalent today. To address this scalability bottleneck, we propose a novel and efficient distributed algorithm. Our approach models the complex ownership structure as a hypergraph, where users are vertices and records are hyperedges. The algorithm proceeds in rounds, allowing users to propose records in parallel. A record is added to the final dataset only if all its owners unanimously agree, thereby ensuring that no user's predefined contribution limit is violated. This method aims to maximize the size of the resulting dataset for high utility while providing a practical, scalable solution for implementing user-level privacy in large, real-world systems. |
| title | Scalable contribution bounding to achieve privacy |
| topic | Data Structures and Algorithms Cryptography and Security Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.23432 |