On Computing Pairwise Statistics with Local Differential Privacy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917703172751360 |
|---|---|
| author | Ghazi, Badih Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sealfon, Adam |
| author_facet | Ghazi, Badih Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sealfon, Adam |
| contents | We study the problem of computing pairwise statistics, i.e., ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $τ$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16305 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Computing Pairwise Statistics with Local Differential Privacy Ghazi, Badih Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sealfon, Adam Data Structures and Algorithms Cryptography and Security We study the problem of computing pairwise statistics, i.e., ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $τ$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries. |
| title | On Computing Pairwise Statistics with Local Differential Privacy |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2406.16305 |