Differentially Private Heavy Hitters

Identifies items that appear more frequently than a user-specified threshold in a data stream. In a non-private setting, this is solved with exact counters. Under differential privacy, the challenge is to report these frequent items while masking the presence of any single user's data contribution.

• Frequency Threshold: A minimum count an item must exceed to be considered 'heavy'.
• Streaming Context: Designed for high-velocity data where storing all raw records is infeasible.
• Privacy vs. Utility: The core trade-off—adding noise to protect privacy can obscure the signal of genuinely popular items.

A foundational mechanism that decomposes the data domain into a binary prefix-tree structure. Instead of querying for specific items directly, the algorithm adds calibrated noise to the counts at each node in the tree. It then identifies heavy hitters by finding the most popular prefixes.

• Hierarchical Decomposition: Breaks down a large domain (e.g., all possible search queries) into manageable sub-domains.
• Consistency Constraints: Post-processing is applied to ensure that a parent node's noisy count is consistent with the sum of its children's counts, reducing error.
• Efficiency: Avoids querying the entire domain, making it computationally feasible for high-dimensional categorical data.

An optimized algorithm for discovering heavy hitters in very large, sparse domains. It works by randomly grouping items into 'fragments' and identifying which fragments contain a heavy hitter before zooming in to find the specific item. This two-stage process dramatically reduces the number of queries to the privacy budget.

• Group Testing: Applies the principle of group testing to efficiently search for frequent items in a sparse space.
• Two-Stage Process: First identifies 'hot' groups of items, then analyzes only those groups to find the specific heavy hitter.
• Scalability: Designed to handle domains with billions of unique items, such as discovering trending URLs or popular IP addresses.

A trust model where the frequency estimation is performed on data that has already been randomized on the user's device. The central server never sees raw inputs. Common LDP protocols for heavy hitters include Randomized Response and RAPPOR, which encode user values into a Bloom filter before flipping bits randomly.

• Zero-Trust Server: The aggregator is assumed to be an adversary; privacy is protected at the source.
• Bloom Filter Encoding: Users encode their item into a bit array, randomize each bit, and send the noisy array to the server.
• Crowd-Sourcing Trends: Enables discovering popular emojis, settings, or performance issues in software without any individual's data being centrally logged.

Instead of directly outputting a list of heavy hitters, a differentially private model of the underlying data distribution is built. A DP-GAN or a probabilistic graphical model can be trained to generate a synthetic dataset that statistically mirrors the original, from which heavy hitters can be extracted without additional privacy loss.

• Model-Based Approach: The privacy budget is spent entirely on training a generative model.
• Post-Processing Immunity: Once the synthetic data is generated, any number of non-private heavy hitter algorithms can be run on it without further degrading the privacy guarantee.
• High Utility: This method often preserves more complex statistical relationships than direct query-based approaches.

A strategy where a coarse, noisy histogram is first generated to identify candidate heavy hitters. A second, more precise round of queries with a dedicated portion of the privacy budget is then used to accurately estimate the frequencies of only those candidates, avoiding wasted budget on infrequent items.

• Two-Phase Queries: Phase 1 identifies candidates; Phase 2 refines their counts.
• Budget Division: The total epsilon (ε) is strategically split between the discovery and refinement phases.
• Adaptive Analysis: The algorithm's behavior in Phase 2 adapts based on the noisy results from Phase 1, requiring careful privacy accounting.

The maximum impact a single record can have on a query's output. In the context of heavy hitters, the sensitivity of a frequency count is typically 1—adding or removing one user changes the count of a single item by exactly one. This low sensitivity is what makes private heavy hitter algorithms efficient, as the noise required is proportional to the sensitivity divided by epsilon. Understanding L1 vs L2 sensitivity is critical for choosing between the Laplace and Gaussian mechanisms.

A zero-trust privacy model where noise is added directly on the user's device before any data reaches the server. For heavy hitters, protocols like RAPPOR and Apple's CMS use randomized response to privatize individual item reports. The aggregator then reconstructs frequency histograms from noisy bits. LDP eliminates the need for a trusted curator but typically requires significantly larger user populations to achieve the same utility as central DP.

A finite, quantifiable resource that tracks cumulative privacy loss across multiple queries. When discovering heavy hitters over streaming data, the budget must be carefully allocated across time windows. Techniques like binary tree aggregation and sparse vector techniques allow analysts to pay privacy cost only when the data actually changes, dramatically extending the lifetime of a privacy budget for continuous monitoring of trending items.

The formal rule governing how privacy guarantees degrade under repeated queries. When computing heavy hitters across multiple time intervals or data slices, the total privacy loss accumulates. Basic composition adds epsilons linearly, while advanced composition provides tighter bounds using the square root of the number of queries. The Moments Accountant offers even sharper bounds, enabling more accurate heavy hitter detection under the same total privacy budget.

A knowledge distillation framework where multiple teacher models trained on disjoint data partitions vote on labels. For heavy hitters, PATE can be adapted so that each teacher identifies frequent items from its own shard, and the noisy aggregation of votes reveals only items with strong consensus. This approach provides strong privacy amplification through the ensemble structure while maintaining high accuracy for truly popular items.