Federated Heavy Hitters Discovery with Differential Privacy

Motivation and contribution

• The approach seeks to bridge central and local DP: it retains federated updates without raw-data collection, while local DP can substantially reduce utility for heavy-hitter discovery.Whether a privacy level is sufficient for a particular application is a domain-dependent policy question beyond the paper’s scope.Source: §1 · p. 1

Contributions

• The algorithm discovers heavy hitters without seeking their frequencies, enabling applications such as adding out-of-dictionary words to a keyboard.Its design targets central DP while minimizing the data collected from users.Source: §1 · p. 2

Algorithm overview

• Each round samples users to vote for one-element extensions of popular prefixes; the server aggregates votes in a trie and prunes nodes below threshold θ.The process continues across rounds to discover longer sequences.Source: §1 · p. 2

Empirical evaluation

• On Sentiment140, the top 200 words are recalled at a rate close to 1 with ε = 4 and δ < 5 × 10−9.The dataset contains 1.6M tweets from over 650k users.Source: §1 · p. 2

Privacy approach

• Random sampling and trie pruning achieve differential privacy without added noise, while fixed-size sampling avoids the variable user counts of Poisson sampling.The authors distinguish this interactive, decentralized approach from methods that reveal sampled users’ entire sequences.Source: §1 · p. 3

Related work

• TrieHH differs from prior trie-based heavy-hitter work by being interactive, not using sketching or public randomness, and not offering local DP.The paper also contrasts its minimal per-round user data with centralized approaches that collect raw data.Source: §1 · pp. 1, 3

Model and notation

• The model has n users, each with a collection of items represented as sequences of elements, with maximum sequence length L.In the experiments, items are words represented as sequences of ASCII characters.Source: §2 · p. 3

Trie notation

• A prefix belongs to a trie when its path exists; growing the trie appends a child node, and T_i contains its first i levels.Source: §2 · pp. 3–4

Differential privacy

• User-level adjacency treats datasets as adjacent when one user’s items are added, a stronger notion than adjacency differing by one item.Source: §2 · p. 4

Paper organization

• The paper presents the single-sequence algorithm and its privacy and utility analysis, then extends to multiple sequences per user and evaluates on Sentiment140.Proofs and additional experiments are deferred to supplementary material.Source: §2 · p. 4

3 Single Sequence per User

• Algorithm 1 samples users in rounds and extends the trie only with prefixes receiving at least θ votes, then outputs discovered sequences ending in the EOS symbol.Each round grows at most one trie level; incomplete non-EOS leaves remain frequent prefixes that may be useful to an application.Source: §3 · p. 5
• The algorithm’s output is (ε, δ)-differentially private without additional randomization or noise, and its discovered sequences are θ-anonymous.The privacy proof bounds the effect of adding one user by showing popular prefixes change little while infrequent prefixes have sufficiently small discovery probability.Source: §3 · pp. 5–6
• For n ≥ 10^4, choosing θ = ⌈log10 n + 6⌉ ensures (ε, 1/(300n))-differential privacy.The algorithm’s parameters can be tuned to obtain precise privacy guarantees.Source: §3 · p. 6
• Smaller batches and larger thresholds improve privacy at the expense of utility; larger batches and smaller thresholds make the opposite trade-off.Discovery probability is evaluated under a worst case in which a sequence shares no prefixes with other sequences; common prefixes can only improve its discovery rate.Source: §3 · p. 6
• For a worst-case discovery rate of at least 0.9, lower-frequency sequences require larger populations, and stronger privacy guarantees also require larger populations.Figure 2 illustrates the population-size relationship for fixed ε.Source: Figure 2 · p. 6, §3 · p. 7

4 Multiple Sequences per User

• Each selected user contributes one randomly chosen sequence, sampled according to its local frequency, before the usual trie voting step.A sequence’s local frequency is its count on that user’s device divided by the total counts of sequences on that device.Source: §4 · p. 7
• The single-sequence differential privacy guarantees also hold when users may have multiple sequences.More generally, selecting one record per user and then applying a record-level (ε, δ)-DP mechanism yields user-level (ε, δ)-DP.Source: §4 · p. 7

Experimental setup

• The experiments use Sentiment140 and compare TrieHH with Apple's SFP using precision, recall, and F1, with averaged metrics and 0.95 confidence intervals.The SFP local ε values are amplified to central (ε, δ) values for comparison; the evaluation covers only SFP's discovery stage.Source: §5 · p. 8

Single word per user: heavy hitters case

• TrieHH's experimental discovery rates exceed the theoretical worst-case bounds because many Sentiment140 words share prefixes.The single-word experiment sets δ=1/n2 and selects θ and γ for varying ε.Source: Figure 3 · p. 8, §5 · p. 9
• At ε=4, the top 100 words have F1 close to 1 under TrieHH versus close to 0.2 under SFP.The comparison is for the single-word setting; SFP uses T=20 in Figure 4.Source: Figure 4 · p. 8, §5 · p. 9

Single word per user: out-of-vocab (OOV) case

• In the OOV setting, both algorithms perform worse on longer words, producing non-monotonic F1 curves for small K.The OOV dataset excludes words in a highly tuned dictionary of over 260k words; increasing SFP's T raises recall but sharply lowers precision.Source: §5 · p. 9, Figure 5 · p. 9

Multiple words per user: heavy hitters case

• At ε=4 and δ < 5 × 10^-9, the top 200 words are recalled at a rate close to 1 in the multiple-words setting.The section notes that a non-trivial lower bound on discovery rate depends heavily on the word distribution.Source: §5 · p. 9, Figure 7 · p. 10

Conclusion

• The proposed federated algorithm learns frequent sequences and is proved inherently differentially private.The paper also investigates the privacy-utility trade-off.Source: §6 · p. 10
• The approach avoids centralizing raw data while avoiding the harsh utility penalty associated with local differential privacy.Source: §6 · p. 10

Open questions

• Open questions include whether interactivity is necessary and how cryptographic tools and local plausible deniability affect privacy guarantees.The paper specifically proposes examining secure multi-party computation, shuffling, threshold oblivious pseudorandom functions, fully homomorphic encryption, and privacy amplification.Source: §6 · p. 10

A Proof of Theorem 1 and Theorem 2

• A uniformly sampled subset’s chance of containing at least θ users with a prefix is computed by summing its hypergeometric probabilities.This probability bound is used in the proof of Lemma 2 and in the privacy–utility analysis.Source: A Proof of Theorem 1 and Theorem 2 · p. 14
• For prefixes with at least θ supporters in the neighboring dataset, the output-trie probability ratio is bounded by 1 + θ/(k − θ + 1).Here k is the number of users in the neighboring dataset with the prefix.Source: A Proof of Theorem 1 and Theorem 2 · pp. 14, 16
• The proof handles neighboring datasets by counting sampled-user selections that produce the same trie, including cases where the differing sequence is selected.It compares those counts for datasets differing in one sequence and separates cases according to how many other users share the prefix.Source: A Proof of Theorem 1 and Theorem 2 · pp. 14–15
• For 4 ≤ θ ≤ √n and γ ≥ 1, the probability that pi(w) appears in M(D, θ, γ), conditional on pi−1(w) appearing there, is at most θ−2 (θ−3)θ!.Source: A Proof of Theorem 1 and Theorem 2 · p. 16

A.1 Proof of Theorem 1

• For |w| = l, S is partitioned by the initial prefixes of w; when j is the smallest index with P(M(D) ∈ Rj) ≤ θ−2 (θ−3)θ!, each P(M(D) ∈ Si) is at most that threshold.Source: §A.1 · p. 18

A.2 Proof of Theorem 2

• Theorem 2’s proof samples one record per user before applying M, then uses M’s record-level differential privacy guarantee to bound the sampled process.The proof writes the output probability as a sum over sampled records and compares neighboring datasets that differ in one user’s record.Source: §A.2 · p. 20

B.1 Proof for Corollary 1

• When n ≥104, the proof chooses θ = ⌈log10 n + 6⌉ and uses θ! ≥ 360n.It notes θ = 10 when n = 104 and that increasing n tenfold increases θ! by more than tenfold.Source: §B.1 · p. 21

C Implementation of SFP

• SFP hashes client strings into a Count Mean Sketch and adds ε-local-DP noise before sending results to the server.The implementation uses m = 1024 and k = 2048 for the sketch, and considers strings up to length 10 by padding or truncation.Source: C Implementation of SFP · p. 21
• SFP forms per-index candidate lists from sketch frequency estimates and combines their entries into the returned heavy hitters.For each index, the server selects the T highest-count tuples before forming Cartesian products by hash value.Source: C Implementation of SFP · p. 21

D.1 Time, Space and Communication Complexity Analysis of TrieHH

• TrieHH’s server running time is O(mL), while user-side prefix searching is bounded in terms of m, Z, and L.The passages also describe trie-sized storage and a worst-case communication cost accumulated across at most L rounds.Source: §D.1 · p. 22

• The section provides the top 200 heavy hitters in Sentiment140 and in the OOV dataset after filtering out dictionary words.Source: §D.2 · p. 22
• In Sentiment140, “the” leads the top-100 list at 0.1028, followed by “you” at 0.0360.Source: §D.2 · p. 22
• In the OOV list generated from Sentiment140, “dont” leads at 0.011741, followed by “thats” at 0.006008.Source: §D.2 · pp. 22–23