Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning Article Swipe
Haorui Wu
,
Hanwen Zhang
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2411.09552
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2411.09552
We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d^{\,Θ(k)}$ possible length-$k$ sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of $\tilde{O}(dk)$. In this paper, we present an improved algorithm with time and space complexity $O(d + k^2 / ε\cdot \ln d)$, where $ε$ denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2411.09552
- https://arxiv.org/pdf/2411.09552
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4404451278
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4404451278Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2411.09552Digital Object Identifier
- Title
-
Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with PruningWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-11-14Full publication date if available
- Authors
-
Haorui Wu, Hanwen ZhangList of authors in order
- Landing page
-
https://arxiv.org/abs/2411.09552Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2411.09552Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2411.09552Direct OA link when available
- Concepts
-
Mechanism (biology), Pruning, Joint (building), Selection (genetic algorithm), Exponential function, Computer science, Mathematics, Artificial intelligence, Biology, Botany, Physics, Engineering, Mathematical analysis, Structural engineering, Quantum mechanicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4404451278 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2411.09552 |
| ids.doi | https://doi.org/10.48550/arxiv.2411.09552 |
| ids.openalex | https://openalex.org/W4404451278 |
| fwci | |
| type | preprint |
| title | Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10237 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9907000064849854 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Cryptography and Data Security |
| topics[1].id | https://openalex.org/T10720 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9790999889373779 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Complexity and Algorithms in Graphs |
| topics[2].id | https://openalex.org/T12072 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9639000296592712 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Machine Learning and Algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C89611455 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7144467234611511 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q6804646 |
| concepts[0].display_name | Mechanism (biology) |
| concepts[1].id | https://openalex.org/C108010975 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6795870661735535 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q500094 |
| concepts[1].display_name | Pruning |
| concepts[2].id | https://openalex.org/C18555067 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6421679854393005 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q8375051 |
| concepts[2].display_name | Joint (building) |
| concepts[3].id | https://openalex.org/C81917197 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6335437893867493 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q628760 |
| concepts[3].display_name | Selection (genetic algorithm) |
| concepts[4].id | https://openalex.org/C151376022 |
| concepts[4].level | 2 |
| concepts[4].score | 0.48012757301330566 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q168698 |
| concepts[4].display_name | Exponential function |
| concepts[5].id | https://openalex.org/C41008148 |
| concepts[5].level | 0 |
| concepts[5].score | 0.4430873394012451 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[5].display_name | Computer science |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.3493974804878235 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C154945302 |
| concepts[7].level | 1 |
| concepts[7].score | 0.28672266006469727 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[7].display_name | Artificial intelligence |
| concepts[8].id | https://openalex.org/C86803240 |
| concepts[8].level | 0 |
| concepts[8].score | 0.26513487100601196 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[8].display_name | Biology |
| concepts[9].id | https://openalex.org/C59822182 |
| concepts[9].level | 1 |
| concepts[9].score | 0.19202253222465515 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q441 |
| concepts[9].display_name | Botany |
| concepts[10].id | https://openalex.org/C121332964 |
| concepts[10].level | 0 |
| concepts[10].score | 0.1564658284187317 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[10].display_name | Physics |
| concepts[11].id | https://openalex.org/C127413603 |
| concepts[11].level | 0 |
| concepts[11].score | 0.13885939121246338 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[11].display_name | Engineering |
| concepts[12].id | https://openalex.org/C134306372 |
| concepts[12].level | 1 |
| concepts[12].score | 0.09993427991867065 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[12].display_name | Mathematical analysis |
| concepts[13].id | https://openalex.org/C66938386 |
| concepts[13].level | 1 |
| concepts[13].score | 0.07396772503852844 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q633538 |
| concepts[13].display_name | Structural engineering |
| concepts[14].id | https://openalex.org/C62520636 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[14].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/mechanism |
| keywords[0].score | 0.7144467234611511 |
| keywords[0].display_name | Mechanism (biology) |
| keywords[1].id | https://openalex.org/keywords/pruning |
| keywords[1].score | 0.6795870661735535 |
| keywords[1].display_name | Pruning |
| keywords[2].id | https://openalex.org/keywords/joint |
| keywords[2].score | 0.6421679854393005 |
| keywords[2].display_name | Joint (building) |
| keywords[3].id | https://openalex.org/keywords/selection |
| keywords[3].score | 0.6335437893867493 |
| keywords[3].display_name | Selection (genetic algorithm) |
| keywords[4].id | https://openalex.org/keywords/exponential-function |
| keywords[4].score | 0.48012757301330566 |
| keywords[4].display_name | Exponential function |
| keywords[5].id | https://openalex.org/keywords/computer-science |
| keywords[5].score | 0.4430873394012451 |
| keywords[5].display_name | Computer science |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.3493974804878235 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[7].score | 0.28672266006469727 |
| keywords[7].display_name | Artificial intelligence |
| keywords[8].id | https://openalex.org/keywords/biology |
| keywords[8].score | 0.26513487100601196 |
| keywords[8].display_name | Biology |
| keywords[9].id | https://openalex.org/keywords/botany |
| keywords[9].score | 0.19202253222465515 |
| keywords[9].display_name | Botany |
| keywords[10].id | https://openalex.org/keywords/physics |
| keywords[10].score | 0.1564658284187317 |
| keywords[10].display_name | Physics |
| keywords[11].id | https://openalex.org/keywords/engineering |
| keywords[11].score | 0.13885939121246338 |
| keywords[11].display_name | Engineering |
| keywords[12].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[12].score | 0.09993427991867065 |
| keywords[12].display_name | Mathematical analysis |
| keywords[13].id | https://openalex.org/keywords/structural-engineering |
| keywords[13].score | 0.07396772503852844 |
| keywords[13].display_name | Structural engineering |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2411.09552 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2411.09552 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2411.09552 |
| locations[1].id | doi:10.48550/arxiv.2411.09552 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2411.09552 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5056932320 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-6314-0452 |
| authorships[0].author.display_name | Haorui Wu |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | WU, Hao |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100332186 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-4973-0242 |
| authorships[1].author.display_name | Hanwen Zhang |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Zhang, Hanwen |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2411.09552 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-11-17T00:00:00 |
| display_name | Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10237 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9907000064849854 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Cryptography and Data Security |
| related_works | https://openalex.org/W2382997850, https://openalex.org/W2373300491, https://openalex.org/W2390968135, https://openalex.org/W2395294869, https://openalex.org/W2378744544, https://openalex.org/W2594301978, https://openalex.org/W2379704676, https://openalex.org/W1998810860, https://openalex.org/W4206442282, https://openalex.org/W2384505857 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2411.09552 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2411.09552 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2411.09552 |
| primary_location.id | pmh:oai:arXiv.org:2411.09552 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2411.09552 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2411.09552 |
| publication_date | 2024-11-14 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.+ | 83 |
| abstract_inverted_index./ | 85 |
| abstract_inverted_index.a | 11, 33, 62 |
| abstract_inverted_index.In | 69 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.an | 74 |
| abstract_inverted_index.by | 26 |
| abstract_inverted_index.et | 28 |
| abstract_inverted_index.of | 13, 41, 67, 103 |
| abstract_inverted_index.or | 54 |
| abstract_inverted_index.to | 9, 51 |
| abstract_inverted_index.we | 72 |
| abstract_inverted_index.$d$ | 22 |
| abstract_inverted_index.$k$ | 14 |
| abstract_inverted_index.\ln | 87 |
| abstract_inverted_index.al. | 29 |
| abstract_inverted_index.and | 64, 79 |
| abstract_inverted_index.has | 61 |
| abstract_inverted_index.k^2 | 84 |
| abstract_inverted_index.our | 99 |
| abstract_inverted_index.the | 2, 18, 38, 92 |
| abstract_inverted_index.$O(d | 82 |
| abstract_inverted_index.$ε$ | 90 |
| abstract_inverted_index.'22) | 31 |
| abstract_inverted_index.d)$, | 88 |
| abstract_inverted_index.from | 21, 37 |
| abstract_inverted_index.pure | 53 |
| abstract_inverted_index.runs | 101 |
| abstract_inverted_index.show | 97 |
| abstract_inverted_index.than | 106 |
| abstract_inverted_index.that | 98 |
| abstract_inverted_index.this | 70 |
| abstract_inverted_index.time | 63, 78 |
| abstract_inverted_index.vast | 39 |
| abstract_inverted_index.with | 16, 77 |
| abstract_inverted_index.work | 25 |
| abstract_inverted_index.(ICML | 30 |
| abstract_inverted_index.Their | 59 |
| abstract_inverted_index.items | 15 |
| abstract_inverted_index.space | 65, 80 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.their | 107 |
| abstract_inverted_index.where | 89 |
| abstract_inverted_index.while | 109 |
| abstract_inverted_index.Recent | 24 |
| abstract_inverted_index.aiming | 8 |
| abstract_inverted_index.direct | 34 |
| abstract_inverted_index.faster | 105 |
| abstract_inverted_index.items. | 23 |
| abstract_inverted_index.orders | 102 |
| abstract_inverted_index.paper, | 71 |
| abstract_inverted_index.scores | 20 |
| abstract_inverted_index.denotes | 91 |
| abstract_inverted_index.employs | 32 |
| abstract_inverted_index.highest | 19 |
| abstract_inverted_index.present | 73 |
| abstract_inverted_index.privacy | 93 |
| abstract_inverted_index.private | 4, 57 |
| abstract_inverted_index.results | 96 |
| abstract_inverted_index.showing | 46 |
| abstract_inverted_index.similar | 111 |
| abstract_inverted_index.top-$k$ | 5 |
| abstract_inverted_index.ε\cdot | 86 |
| abstract_inverted_index.accuracy | 49 |
| abstract_inverted_index.approach | 36 |
| abstract_inverted_index.compared | 50 |
| abstract_inverted_index.identify | 10 |
| abstract_inverted_index.improved | 75 |
| abstract_inverted_index.methods. | 58 |
| abstract_inverted_index.possible | 43 |
| abstract_inverted_index.previous | 52 |
| abstract_inverted_index.problem, | 7 |
| abstract_inverted_index.sampling | 35 |
| abstract_inverted_index.sequence | 12 |
| abstract_inverted_index.superior | 47 |
| abstract_inverted_index.accuracy. | 113 |
| abstract_inverted_index.achieving | 110 |
| abstract_inverted_index.algorithm | 60, 76, 100 |
| abstract_inverted_index.approach, | 108 |
| abstract_inverted_index.empirical | 48, 112 |
| abstract_inverted_index.magnitude | 104 |
| abstract_inverted_index.selection | 6 |
| abstract_inverted_index.collection | 40 |
| abstract_inverted_index.complexity | 66, 81 |
| abstract_inverted_index.length-$k$ | 44 |
| abstract_inverted_index.parameter. | 94 |
| abstract_inverted_index.sequences, | 45 |
| abstract_inverted_index.Gillenwater | 27 |
| abstract_inverted_index.approximate | 55 |
| abstract_inverted_index.Experimental | 95 |
| abstract_inverted_index.$d^{\,Θ(k)}$ | 42 |
| abstract_inverted_index.approximately | 17 |
| abstract_inverted_index.differentially | 3, 56 |
| abstract_inverted_index.$\tilde{O}(dk)$. | 68 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |