PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally Differentially Private Heavy Hitter Identification

Tianhao Wang, Ninghui Li, Somesh Jha

arXiv:1708.06674v1cs.CR

TL;DR

Large domains make identifying heavy hitters by querying every value computationally infeasible. The paper proposes and analyzes LDP protocols for this problem, and reports empirical evidence for their effectiveness, including a URL result at ǫ = 4.

  • Problem

    When the input domain is large, estimating every value’s frequency to find heavy hitters is computationally infeasible.

    Source: §I · p. 1, §III · p. 3

  • Method

    The paper proposes and analyzes LDP protocols for identifying heavy hitters in large domains.

    Source: §I · p. 2, §III · p. 3

  • Results

    At ǫ = 4, PEM achieves F1 = 0.9 and identifies more than ten frequent URLs, while MCM and SPM identify two.

    Source: 1) Effect of · p. 11

  • Takeaways & Limitations

    The analysis identifies two design principles intended to guide protocol design for other LDP problems.

    Source: §I · p. 2

    Performance depends heavily on the distribution, and the proposed protocols require a fixed domain.

    Source: §VIII · p. 14

Abstract

from arXiv · show

The notion of Local Differential Privacy (LDP) enables users to answer sensitive questions while preserving their privacy. The basic LDP frequent oracle protocol enables the aggregator to estimate the frequency of any value. But when the domain of input values is large, finding the most frequent values, also known as the heavy hitters, by estimating the frequencies of all possible values, is computationally infeasible. In this paper, we propose an LDP protocol for identifying heavy hitters. In our proposed protocol, which we call Prefix Extending Method (PEM), users are divided into groups, with each group reporting a prefix of her value. We analyze how to choose optimal parameters for the protocol and identify two design principles for designing LDP protocols with high utility. Experiments on both synthetic and real-world datasets demonstrate the advantage of our proposed protocol.

I. INTRODUCTION

The introduction frames heavy-hitter identification in large domains as a computational challenge for LDP frequency-oracle methods. It presents a prefix-based protocol, analyzes its design, and reports empirical support for its effectiveness and broader design principles.

A. Differential Privacy in Local Setting

  • LDP lets users report perturbed data so statistics can be gathered without trusting a single data curator.The introduction cites RAPPOR as a deployed example for collecting users’ browser-setting answers.Source: §I · p. 1

I. INTRODUCTION

  • Large domains make querying every possible value computationally infeasible, motivating a protocol to identify candidate frequent values first.Frequency oracles can reconstruct a noisy distribution when the domain is small, but not when enumerating its values is infeasible.Source: §I · p. 1
  • PEM identifies frequent values by extending candidate prefixes across user groups until it finds frequent full values.Each successive group reports longer prefixes; the aggregator uses earlier frequent prefixes to restrict later candidates.Source: §I · p. 1
  • The segment length η trades computational cost and candidate count against utility, and the analysis concludes that larger η improves utility.The authors say this choice depends on computational-resource limits and that empirical experiments validate the analysis.Source: §I · pp. 1–2
  • The analysis identifies two LDP design principles: partition users across multiple questions and minimize the number of groups to improve accuracy.The authors expect these principles to guide protocols for other LDP problems.Source: §I · p. 2

B. Frequency Oracles

III. PROBLEM DEFINITION AND EXISTING METHODS

The section states the large-domain heavy-hitter problem under LDP: querying every possible value can be computationally infeasible. It assumes binary-string inputs for simplicity, while allowing extension to more complex values.

III. PROBLEM DEFINITION AND EXISTING METHODS

  • When the domain is large, enumerating every value to identify frequent values is computationally infeasible.The section notes that a 128-bit domain would require 2^128 oracle queries under the naive approach.Source: §III · p. 3
  • The target is to identify a computationally manageable candidate set whose frequencies can then be queried.The section frames this as identifying frequent values under LDP for a large input domain.Source: §III · p. 3
  • For simplicity, the section represents each value as a binary string, while noting the method can be adapted to values with multiple components.Source: §III · p. 3

A. Problem Definition

The task is to identify top-k frequent values without querying every value in a large domain. Segment-based methods reduce the search, but the strawman candidate set can still be too large, while SPM filters candidates using segment pairs.

A. Problem Definition

  • When the domain is large, querying every value is computationally infeasible; the paper frames heavy hitters as the top-k values, with a frequency threshold approximately translatable to k.For 128-bit strings, querying every value requires 2^128 oracle queries.Source: A. Problem Definition · p. 4

B. Strawman Method

  • The strawman partitions values into segments, finds frequent patterns in each, and combines them by Cartesian product, yielding k^g candidates when it selects k patterns per segment.The resulting candidate set can remain too large to enumerate when the domain and number of segments are large.Source: B. Strawman Method · p. 4

C. The Segment Pairs Method (SPM) [17]

  • SPM has users report pairs of segments, then filters whole-value candidates by retaining values whose segment pairs are frequent.Its limitation is that many segment pairs divide users across locations, making frequent-pair identification difficult when the domain is large.Source: C. The Segment Pairs Method (SPM) [17] · p. 4, Figure 1 · p. 5

D. The Multiple Channel Method (MCM) [6]

MCM uses hash-based channels to isolate candidate frequent values, but reporting a single bit per user limits the data available for recovering each value. PEM instead extends prefixes across groups, reducing the number of groups needed for long strings.

D. The Multiple Channel Method (MCM) [6]

  • MCM hashes values into channels expected to contain at most one frequent value, then recovers a candidate in each channel by taking majority votes over reported bits.The aggregator queries the candidate values' frequencies and outputs frequent ones.Source: D. The Multiple Channel Method (MCM) [6] · p. 5
  • MCM's single-bit reports leave few users to determine each bit, and every bit must be recovered correctly; reporting larger blocks can improve accuracy.Identifying one candidate per channel also multiplies communication and computation overhead by the number of channels.Source: D. The Multiple Channel Method (MCM) [6] · p. 5

A. Prefix Extending Method (PEM)

  • PEM uses overlapping segments as prefixes: each user group reports a prefix, and the aggregator extends frequent prefixes into candidates for the next step.The final group identifies frequent full values; the paper focuses on binary strings, while noting that segmentation can use domain-specific structure.Source: §IV · p. 5, A. Prefix Extending Method (PEM) · p. 6

IV. PROPOSED SOLUTION

  • For long strings, PEM requires only g user groups, whereas SPM and MCM divide users among segment pairs or channels.The cited comparison describes the methods' reporting and candidate-generation arrangements.Source: §IV · p. 5

B. Protocol Analysis

The analysis compares PEM parameters using top-k identification probabilities and utility measures, balancing group size against the number of candidates tested at each step. It estimates those probabilities from noisy frequency-support counts under simplifying assumptions.

Parameter choice

  • Larger η means fewer groups and more users per group, improving estimation accuracy, but also more candidates per step and greater chance of identifying a non-heavy hitter.The analysis treats γ and η as positive parameters and describes γ slightly larger than η as a way to keep candidate-set sizes roughly similar across steps.Source: B. Protocol Analysis · p. 6

Utility metrics

  • F-measure evaluates top-k set overlap, while NCR uses true rank information so missing the highest-ranked value is penalized more than missing another top-k value.Both metrics range from 0 to 1, with higher values indicating better accuracy.Source: 1) Metric · p. 6

Approximate identification probability

  • The analysis models each value's support count as a sum of Bernoulli trials and approximates it with a normal distribution when the group is large enough.The mean support probability combines the value's true frequency with the oracle's support probabilities for matching and nonmatching users.Source: 3) Approximate Identification… · p. 7
  • To estimate top-k identification probability, the analysis sets a threshold using tested non-heavy values and assumes those values have zero frequency.It also assumes heavy-hitter identifications are mutually independent, acknowledging this is technically inexact but expected to have a small effect when k is not very small.Source: 1) Metric · p. 6, 3) Approximate Identification… · p. 7

C. Instantiate PEM

PEM is instantiated by optimizing η under a query limit and assumed data distribution; the analysis yields design principles for LDP protocols. It recommends splitting users across questions and minimizing the number of groups, while balanced allocations are best in the examined cases.

C. Instantiate PEM

  • Optimization assumes a dataset distribution and limits the total frequency-oracle queries; it evaluates η choices using k, m, n, and ε.The best-utility configuration is selected from the calculated utility scores.Source: C. Instantiate PEM · p. 7
  • The utility calculation assumes a distribution, such as Zipf, because heavy-hitter frequency differences affect the utility measure.The analysis also caps the number of frequency-oracle queries.Source: C. Instantiate PEM · p. 7
  • Changing γ, candidate sizes, user allocations, or step-specific η has little effect, but very small η substantially degrades utility.The number of groups is the parameter that affects utility most in the reported optimization.Source: C. Instantiate PEM · p. 7
  • The usual optimized configuration sets γ = log2 k, |Ci| = k, equal-sized groups, and a common maximal η within the query limit.For very large k, the candidate size may be smaller than k; for small k, it may be larger to increase the chance of including heavy-hitter prefixes.Source: C. Instantiate PEM · p. 7

D. Observations and Design Principles

  • In LDP, divide the user population across questions rather than splitting each user's privacy budget among them.The proposition states that this increases identification probability; in centralized DP, the two approaches are generally equivalent in utility.Source: D. Observations and Design Principles · p. 8
  • Within the query limit, the greatest identification probability comes from using the fewest groups.The analysis also recommends making η as large as possible within the query limit when multiple groups are necessary.Source: D. Observations and Design Principles · p. 8
  • When either group size or segment length is balanced, the best result balances the other as well.Specifically, equal user allocation is best when η[i] = m/g, and η[i] = m/g is best when users are equally allocated.Source: D. Observations and Design Principles · p. 8
  • The balanced-allocation observations do not establish the theoretical optimum when both n[i] and η[i] are unbalanced.The authors say these observations are difficult to prove and provide empirical support in the following section.Source: D. Observations and Design Principles · p. 8

V. VALIDATION OF ANALYSIS

Experiments validate that the analytical identification-probability and utility calculations track empirical results across tested settings. They also show how utility varies with privacy and data parameters, group configurations, and the tested distributions.

A. Identification Probability.

B. Utility Scores under Different Configurations.

V. VALIDATION OF ANALYSIS

C. Optimal Utility Scores under Different Scenarios.

  • In unfavorable settings—small ε or n, or large m—Zipf performs better, while zipfs(-20) is similar or better at the other extreme.The paper attributes the difference to which distribution has more significant or more frequent heavy hitters under those settings.Source: Figure 4 · p. 9, C. Optimal Utility Scores under… · p. 10

B. Utility Scores under Different Configurations.

  • More rounds worsen the overall result when each round outputs 16 candidates.The experiment varies the number of rounds from one to six.Source: B. Utility Scores under Different… · p. 9
  • With two rounds, utility is optimal when segment lengths are balanced and when users are split equally between rounds.For the tested settings, the segment-size result is symmetric around η[1] = 6, and the user-allocation result around n[1] = 50000.Source: B. Utility Scores under Different… · p. 9

VI. EVALUATION

The evaluation compares PEM with MCM and SPM on real-world and synthetic data, testing overall utility and the effects of key design choices. PEM outperforms the alternatives in the reported comparisons, while larger segment lengths improve utility subject to a query limit.

A. Evaluation Setup

  • The evaluation uses frequent URLs, AOL queries, and synthetic data, and compares PEM with MCM and SPM after adapting the competitors for a top-k comparison.The synthetic dataset has one million 64-bit values; PEM is optimized assuming a Zipf distribution, with a limit of 2^20 frequency-estimator queries and F1 as its goal.Source: A. Evaluation Setup · p. 10

B. Detailed Results

  • At ε = 4, PEM achieves F1 = 0.9 on frequent URLs, identifying more than ten frequent URLs, while MCM and SPM identify only two.The authors report that PEM performs best among the three protocols as ε varies.Source: 1) Effect of · p. 11
  • PEM outperforms MCM and SPM as k varies; on synthetic data it achieves almost full utility through k = 30.For most cases, utility decreases with k because less frequent values are harder to identify; F1 and NCR are closely correlated.Source: 2) Effect of k · p. 11
  • At θ = 0.023, PEM performs better than SPM and MCM, with its advantage most pronounced at ε = 2.The evaluation varies ε and θ and reports similar results on other datasets.Source: 3) Comparison of Threshold Version · p. 11
  • At ε = 1.2, partitioning users for final testing raises MCM’s F1 from below 0.2 to nearly 0.8.The modified algorithms allocate 10% of users to final testing instead of splitting the privacy budget; the reported trend is similar in other settings.Source: 4) Effect of Partitioning Users · p. 11
  • At ε = 0.9, PEM’s F1 rises from 0.4 at η = 2 to 0.8 at η = 10, though the query limit constrains η.The authors report better overall utility as η increases.Source: 4) Effect of Partitioning Users · p. 11
  • PEM achieves estimation accuracy similar to MCM despite using only the last group, one sixth of users, for estimation.MCM has lower variance than SPM; the paper attributes this to MCM using half of ε for final testing versus one third for SPM.Source: 6) Comparison of Estimation Accuracy · p. 11
  • Results under different distribution assumptions are very similar, except that the authors caution that extreme cases may be affected more.The experiments optimize PEM assuming a Zipf distribution, though the real distribution may be difficult to know.Source: 7) Effect of Distribution Assumption · p. 11

VII. RELATED WORK

Related work spans centralized and local methods for finding heavy hitters, along with local frequency-estimation mechanisms and applications. The paper compares PEM with existing local protocols and distinguishes a simultaneous approach that also extends prefixes.

VII. RELATED WORK

  • For large domains, OLH and OUE are reported to have lower variance than other frequency-estimation mechanisms, including RAPPOR and BLH.These mechanisms are used to estimate value frequencies, a basic tool for several LDP problems.Source: §VII · p. 12
  • Centralized heavy-hitter methods use sketches to track candidates and counts before publishing results with noise, but local protocols face the additional challenge of obtaining candidates.The paper compares PEM with MCM and SPM.Source: §VII · pp. 12–13
  • Among existing local heavy-hitter protocols, Hsu et al. and Mishra et al. have error bounds reported as higher than MCM, while SPM is another comparison method.The paper's experimental comparison is with MCM and SPM.Source: §VII · p. 13
  • A simultaneous method [5] resembles PEM but has each group report one incremental bit, dividing users into m groups.The paper notes that this line of work is motivated by applications where m is large.Source: §VII · p. 13
  • The paper identifies LDP applications involving itemsets,, numerical answers [26], location, weighted histograms, and frequent items.It suggests that insights from its work could improve solutions to these problems.Source: §VII · p. 13

VIII. CONCLUSIONS

The paper concludes that its analyzed and optimized LDP protocols identify heavy hitters in large domains, and that its design principles may guide other LDP problems. It also identifies distribution dependence and fixed domains as limitations of current solutions.

VIII. CONCLUSIONS

  • The paper proposes LDP protocols for identifying heavy hitters in large domains and reports analysis, optimization, and empirical validation on synthetic and real-world data.The authors present design principles as potential guidance for other LDP problems.Source: §VIII · p. 14
  • Current solutions rely heavily on the distribution, and unfavorable distributions can lead to poor results.The authors identify protocols that work well for any distribution as an open direction.Source: §VIII · p. 14
  • All protocols proposed require a fixed domain; handling an unbounded domain and using domain-specific knowledge are identified as future directions.Source: §VIII · p. 14

APPENDIX

The appendix discusses a simpler procedure for joint estimation in SPM and extends it to multiple answers. It also presents a comparison in the proof of Proposition 1, reporting that the numerical calculation supports P1 > P2 in most cases.

APPENDIX

  • The proof argues P1 > P2 when B is assumed near zero and E(ε/g) < E(ε)/g; numerical calculation supports P1 > P2 in most cases.The appendix states the inequality E(ε/g) < E(ε)/g as Lemma 1.Source: APPENDIX · p. 15
  • The simpler joint-estimation procedure is offered as an alternative to SPM’s slow MLE loop over possible combinations.The appendix says the MLE loop terminates only when accumulated updates are small.Source: APPENDIX · p. 15
  • The procedure estimates a pattern pair’s joint count using partial segment estimates and its expected support; the resulting estimate is unbiased.Source: APPENDIX · p. 15
  • The joint-estimation method is stated to extend to more than two answers.Source: APPENDIX · p. 15

Related papers

Loading 1708.06674v1…