Practical Locally Private Heavy Hitters

1 Introduction

• Local privacy randomizes each user’s information before analysis, but its higher noise requires large participant populations and low user-side complexity.The local model avoids a central repository, while estimating quantities can require Ω_ϵ(√n) noise rather than curator-model O_ϵ(1) noise.Source: §1 · pp. 1–2

Our contributions

• TreeHist and Bitstogram target near-optimal locally private heavy-hitters accuracy while minimizing time, space, and communication complexity.TreeHist was implemented and measured against RAPPOR, with better noise-level performance reported under a setting favorable to RAPPOR.Source: §1 · p. 2
• ˜O(n) server time replaces Bassily and Smith’s O(n5/2), while user time falls from O(n3/2) to O(max (log n, log d)2).Bassily and Smith provide matching worst-case error bounds but their user and server runtimes limit practicality.Source: §1 · p. 2
• Bitstogram achieves optimal worst-case error, whereas TreeHist is near-optimal by a factor of √n.Both algorithms have similar performance up to small factors, according to Table 1.Source: §1 · p. 2, Table 1 · p. 2

TreeHist

• TreeHist scans a binary prefix tree, pruning nodes that cannot prefix heavy hitters and querying a frequency oracle at each level.The algorithm recovers heavy hitters bit by bit, then makes a final frequency-oracle query for more accurate estimates.Source: §1 · pp. 2–3

Bitstogram

• Bitstogram hashes the domain to roughly √n buckets and recovers all bits of non-colliding heavy hitters in parallel through frequency-oracle counts.For a heavy hitter without collisions, the count associated with its bit is significantly larger than the opposite-bit count.Source: §1 · p. 3

2.1 Definitions and Notation

• A frequency oracle estimates the frequency of any queried domain item, while a succinct histogram lists frequent items and their estimated frequencies.Items omitted from the list are implicitly assigned estimated frequency zero, and the list need not exceed O(1/η) items for ℓ∞ error η.Source: §2.1 · p. 3

2.2 Local Differential Privacy

• In the local model, each user’s value is accessed only through a randomized localizer, protecting privacy even if all reports are revealed.The definition requires the resulting algorithm to satisfy ϵ-differential privacy for neighboring databases.Source: §2.2 · p. 3

2.3 Count Sketch and Hadamard Transform

• Count sketch uses hashed signed counters and a median estimate to identify frequent elements in a data stream.The sketch updates counters for each sample and estimates an item from hashed counter values across t hash-function pairs.Source: §2.3 · pp. 3–4
• The Hadamard transform followed by sampling compresses client-to-server transmission and reduces protocol space requirements.Its normalized matrix entries are ±1, and any entry can be computed in O(log m) time.Source: §2.3 · p. 4

2.4 Error correction codes

• A ζ-decodable binary (n, k)-code recovers the encoded message when the received word differs in at most ζn positions.For constant ζ < 1/4, constructions have n = O(k) and linear-time encoding and decoding.Source: §2.4 · p. 4

2.5 Tools from Probability

• The paper uses k-wise independence, Poisson approximation, and Poisson tail bounds to control probabilistic events in its analyses.Poisson approximation models bin loads with mean n/R, while the stated tail bound bounds Pr[X ≥ µ(1 + α)] for 0 ≤ α ≤ 1.Source: §2.5.1 · p. 4, §2.5.2 · p. 4

3.1.1 A local randomizer: LocalRnd

• TreeHist's LocalRnd hashes a prefix or full item, samples a Hadamard-transformed signal, and applies randomized response before sending one bit.It is described as a compressed, sampled, randomized version of count sketch, reducing space and communication requirements.Source: §3.1.1 · pp. 5–6

3.1.2 A frequency oracle: FreqOracle

• FreqOracle reconstructs compressed noisy signals for each hash pair, estimates frequencies, and takes their median for a high-confidence result.The procedure collects reports assigned to matching prefix and hash indices, applies an inverse Hadamard transform, and aggregates signed estimates.Source: §3.1.2 · p. 6

3.1 The TreeHist Protocol

• TreeHist scans a binary prefix tree, pruning nodes that cannot prefix heavy hitters and then estimating surviving items more accurately.The final estimation phase reduces sampling variance by partitioning users across hash pairs rather than across tree levels and hash pairs.Source: §3.1.3 · p. 6

3.1.3 The protocol: TreeHist

• TreeHist's pruning phase limits each level's surviving nodes and uses a second frequency-oracle pass to improve the selected heavy hitters' frequency estimates.The construction guarantees a bounded number of surviving nodes at each level, reducing the queried search space.Source: §3.1.3 · p. 6

3.1.4 Privacy and Utility Guartantees

• TreeHist is ϵ-locally differentially private and, with probability at least 1 −β, outputs a list satisfying its stated frequency and inclusion guarantees.The supplied guarantee passages state that low-frequency items are excluded and output frequency estimates have bounded error.Source: §3.1.4 · pp. 6–7

3.2 The Bitstogram Protocol

• Bitstogram queries a frequency oracle only for roughly √n elements instead of scanning the full domain, then estimates frequencies for the identified candidates.This restriction is intended to avoid frequency-oracle runtime linear in the domain size.Source: §3.2 · pp. 7–8
• Bitstogram hashes the domain so that a heavy hitter can be isolated, then recovers its bits by comparing the frequencies of the two bit values in its hash bucket.The method assumes the relevant heavy hitter does not collide with other heavy hitters; a frequency oracle then identifies the more frequent bit at each coordinate.Source: §3.2 · pp. 7–8
• Bitstogram satisfies ϵ-LDP and returns a list of length ˜O(√n) with the stated inclusion and frequency-accuracy guarantees.The supplied result passages include the algorithm's privacy lemma and separate guarantees for candidate inclusion and estimated frequencies.Source: §3.2 · p. 8

4.1 Private Frequency Oracle

• Frequency estimates are unbiased on synthetic data, with each percentile’s average estimate within one standard deviation of its true value.The experiment uses d = 100, n = 10 million, and averages results over ten runs.Source: §4.1 · p. 8, Figure 1 · p. 9
• Estimation error decreases significantly as the sample count n or privacy parameter ϵ increases.Figure 1 varies n and ϵ on a synthetic power-law data set.Source: §4.1 · p. 8, Figure 1 · p. 9
• Changing the sketch width m produces results that are seemingly insensitive to the hash-function range.Figure 2 evaluates this variation on the synthetic data set.Source: §4.1 · p. 8, Figure 2 · p. 9
• On the NLTK-Brown corpus, frequency-estimation behavior is consistent with the synthetic-data experiment.The corpus experiment uses n = 10 million samples drawn with replacement and the same default system parameters.Source: §4.1 · p. 9, Figure 3 · p. 10
• Higher frequencies are estimated similarly by RAPPOR and TreeHist, while TreeHist is closer to true values in lower-frequency regimes.The authors do not claim TreeHist outperforms RAPPOR on all problem instances and call for an at-scale comparison.Source: §4.1 · p. 9

4.2 Private Heavy-hitters

• Heavy-hitter experiments use unknown domains, a threshold of 15 · √n, and precision and recall to evaluate identification.Recall is much better than precision because the evaluation contains 3 × 10^8 negative examples; false positives can be pruned using domain expertise.Source: §4.2 · p. 10, Table 2 · p. 10

5.1 A Local Randomizer: LocalRnd

• The local randomizer transforms and samples Count-Sketch signals with a Hadamard matrix, preserving accuracy while reducing space and communication; each invocation sends 1 bit and users send 2 bits overall.LocalRnd is invoked once during pruning and once during final estimation, using the Final flag to distinguish prefix reports from full-item reports.Source: §5.1 · pp. 11–12

5.2 A Frequency Oracle: FreqOracle

• FreqOracle reconstructs Count-Sketch-style frequency estimates by inverse-transforming compressed noisy reports and taking the median across hash indices.This recovers Count-Sketch functionality with less space and communication by sampling in the Hadamard/Fourier domain before server-side reconstruction.Source: §5.2 · p. 13

5.3 Succinct Histogram via a Tree Aggregation Protocol: TreeHist

• TreeHist outputs a succinct histogram of heavy hitters with frequency estimates, using pruning followed by a final estimation phase.The protocol scans a prefix tree, retains plausible heavy-hitter prefixes, and re-estimates surviving items with lower sampling variance in the final phase.Source: §5.3 · pp. 13–14
• TreeHist prunes prefix-tree nodes that cannot lead to heavy hitters, then applies FreqOracle only to surviving children before estimating the final candidates more accurately.The final phase partitions users across hash pairs rather than across all prefix-level bins, reducing sampling variance.Source: §5.3 · pp. 13–14

5.4 Running Time and Processing Memory

• The implementation reduces TreeHist’s direct approximately n^1.5 computation to approximately n server time by reusing aggregated sums across the protocol.FreqOracle is invoked O(log d) times, once per tree level and once for final estimation.Source: §5.4 · p. 14

5.5 Privacy and Utility Guartantees

• TreeHist is epsilon-locally differentially private and, with probability at least 1 − β, excludes items below the threshold η while providing bounded frequency-estimation error.The guarantees rely on the protocol’s hash, partition, row-index, and privacy randomization under stated parameter conditions.Source: §5.5 · pp. 15–16
• Poisson concentration gives |γ f̃Ij(v) − f(v)| ≤ 4√nγ and n/2 ≤ γ ñIj ≤ 2n with probability at least 0.996.These concentration bounds support the subsequent collision and frequency-estimation guarantees.Source: §5.5 · p. 16
• With probability at least 1 − β 3 log d, uniformly for all v ∈ bV, |G1(v)| ≥ 9/10t and |G2(v)| ≥ 4/5t.Source: §5.5 · pp. 16, 18
• 14√nγ/ϵ bounds |f̂(v) − f(v)| for every v ∈ bV with probability at least 1 − β log d.The final estimate is the median of the t frequency estimates generated by FreqOracle.Source: §5.5 · p. 18

6.1 Warmup: A Simple Protocol for Heavy-Hitters

• The warmup protocol partitions users across bit positions, estimates hashed bit frequencies, reconstructs one candidate per hash cell, and then estimates each candidate’s full frequency.The section presents this construction as a simplification before later modifications reduce worst-case error, space complexity, and time complexity.Source: §6.1 · p. 19, §6.1.2 · p. 20

6.1.1 Frequency Oracle

• The basic frequency oracle randomizes each user’s bit by flipping it with probability 1/(eϵ + 1), then estimates frequencies from randomized responses and public randomness.ExplicitHist’s concentration analysis applies simultaneously to a queried subset through union bounds, with pairwise or k-wise independence sufficient for the public matrix.Source: §6.1.1 · pp. 19–20

6.1.2 A Simple Heavy Hitters Protocol

• SuccinctHist returns a list L of length T such that, with probability 1 − β, every (v, a) ∈ L satisfies |a − fS(v)| ≤ 6ϵ, and every v ∈ V with fS(v) ≥ w is in L with probability 1/2.Source: §6.1.2 · p. 20

6.2.1 Space and Time Efficient Frequency Oracle

• Hashtogram satisfies ϵ-LDP and answers queried frequencies using multiple hash functions, random user partitions, local randomization, and a median of per-hash estimates.The analysis relies on most hash functions having limited collisions and sufficiently populated partitions, enabling accurate estimates under the stated parameter conditions.Source: §6.2.1 · pp. 21–22
• For ε≤1, Hashtogram, queried on V with d′≤d, uses R≥300 log(12nd′/β), n≥43R, and T≥ε·n/log(nd′/β), answering every v∈V with probability at least 1−β.Source: §6.2.1 · p. 21
• Hashtogram answers every queried value with error(v*) by taking the median of hashed estimates, while its optimized implementation runs in approximately n log n time.Pairwise-independent hash columns reduce the direct implementation from approximately n^1.5 time to approximately n log n.Source: §6.2.1 · p. 24

6.2.2 The Full Protocol

• Bitstogram satisfies ε-LDP and returns a list L containing accurate estimates while including every sufficiently frequent value with probability 1 − β.The protocol uses binary error-correcting codes and hashed bitwise frequency estimates to recover heavy hitters despite some inaccurate oracle queries.Source: §6.2.2 · p. 24

T . Let R1, R2, Rv∗

• Bitstogram runs in approximately n time and uses approximately √n processing memory by streaming frequency-oracle results and discarding low-frequency candidates.The protocol instantiates O(R · log d) Hashtogram copies, performs approximately n queries, and retains only candidates above the √n threshold.Source: T . Let R1, R2, Rv∗ · p. 28

• Each invocation of LocalRnd is ε/2-locally differentially private for any pair of user inputs and output bits.Source: §A.1 · p. 30
• TreeHist is ε-differentially private because each user invokes LocalRnd only twice, with separate pruning and final phases.Source: §A.1 · p. 30

• With probability at least 1 − β, every tree level retains prefixes with frequency at least η and includes all prefixes with frequency above 3η.The argument maintains at most 2n/η surviving nodes at each level through an induction over the tree.Source: §A.2 · p. 30
• During the final phase, TreeHist applies the frequency oracle to surviving final-level nodes and obtains bounded estimation error with probability at least 1 − β/log(d).This establishes the theorem’s final estimation guarantee for the identified candidates.Source: §A.2 · p. 30

• Hashing yields at least 7R/8 repetitions in which each queried item has limited collision with other inputs, with probability at least 1 − β.This is established using Markov, Chernoff, and a union bound over queries and hash functions.Source: §B.1 · p. 31
• Randomly partitioning users produces balanced subsets, with n/(2R) ≤ |I_r| ≤ 2n/R for every r with probability at least 1 − β.The balance condition assumes n ≥ 8R log(2R/β).Source: §B.1 · p. 31
• For each query, sampled hash-based estimates are accurate on at least 7R/8 repetitions, and their median therefore approximates the true frequency.The proof combines concentration over the sampled local randomizers with a Chernoff bound and a union bound.Source: §B.1 · pp. 31–32
• For every v∗ ∈ V simultaneously, with probability at least 1 − β, Inequality (5) holds for at least 7R/8 choices of r ∈ [R].This conclusion uses the condition R ≥ 132 ln(d′/β).Source: §B.1 · p. 32