# Private Frequency Estimation via Projective Geometry

arXiv: https://arxiv.org/abs/2203.00194 · HTML: https://mlsanity.com/paper/2203.00194/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 23 references that are in the map.
- First posted on arXiv 1 Mar 2022.

## Builds on (most cited first, 16 of 16)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Optimal locally private estimation under ℓp loss for 1≤ p≤ 2](https://mlsanity.com/paper/1810.07283/) (2018)

## Built on by (most cited first, 9 of 9)

- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Samplable Anonymous Aggregation for Private Federated Data Analysis](https://mlsanity.com/paper/2307.15017/) (2023)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Consistent Estimation of Numerical Distributions under Local Differential Privacy by Wavelet Expansion](https://mlsanity.com/paper/2509.19661/) (2025)
- [Private Frequency Estimation Via Residue Number Systems](https://mlsanity.com/paper/2511.11569/) (2025)

## Abstract (arXiv)

In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of k and with n users, our varepsilon-LDP algorithm has communication cost lceillog2krceil bits in the private coin setting and varepsilonlog2 e + O(1) in the public coin setting, and has computation cost O(n + kexp(varepsilon) log k) for the server to approximately reconstruct the frequency histogram, while achieving the state-of-the-art privacy-utility tradeoff. In many parameter settings used in practice this is a significant improvement over the  O(n+k2) computation cost that is achieved by the recent PI-RAPPOR algorithm (Feldman and Talwar; 2021). Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR while using approximately 75x less memory for practically relevant parameter settings. In addition, the running time of our algorithm is within an order of magnitude of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. The error of our algorithm essentially matches that of the communication- and time-inefficient but utility-optimal SubsetSelection (SS) algorithm (Ye and Barg; 2017). Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction on the server side. We also give an extension of PGR, which we call HybridProjectiveGeometryResponse, that allows trading off computation time with utility smoothly.