Abstract: The notion of Local Differential Privacy (LDP) enables users to respond to sensitive questions while preserving their privacy. The basic LDP frequent oracle (FO) protocol enables an aggregator to estimate the frequency of any value. But when each user has a set of values, one needs an additional padding and sampling step to find the frequent values and estimate their frequencies. In this paper, we formally define such padding and sample based frequency oracles (PSFO). We further identify the privacy amplification property in PSFO. As a result, we propose SVIM, a protocol for finding frequent items in the set-valued LDP setting. Experiments show that under the same privacy guarantee and computational cost, SVIM significantly improves over existing methods. With SVIM to find frequent items, we propose SVSM to effectively find frequent itemsets, which to our knowledge has not been done before in the LDP setting.
Introduction
Local Differential Privacy (LDP) has become the gold standard for privacy-preserving data collection, adopted by major technology firms like Apple and Google. LDP ensures that individual data remains private by adding noise at the source—the user's device—before it is ever sent to a central server. While current LDP protocols are effective for single-value data (e.g., "What is your favorite emoji?"), they face significant challenges when dealing with set-valued data (e.g., "Which emojis did you use today?").
In set-valued scenarios, reporting an entire set of items causes the privacy leakage (parameter $\epsilon$) to multiply with each item reported. To mitigate this, researchers typically employ "padding and sampling": users pad their set to a fixed size $\ell$ and report only one randomly sampled item. However, this approach introduces bias (under-estimating true frequencies) and high noise levels that often obscure all but the most frequent items.
The SVIM and SVSM Protocols
To address these limitations, this research introduces a formal framework for Padding-and-Sampling Frequency Oracles (PSFO) and two novel protocols: SVIM (Set-Value Item Mining) and SVSM (Set-Value itemSet Mining).
SVIM (Set-Value Item Mining)
SVIM is a four-step iterative process designed to identify individual frequent items with high accuracy:
- Pruning: Uses a minimal padding size ($\ell=1$) to rapidly identify a candidate set of frequent items.
- Size Estimation: A subset of users reports their set sizes to determine the 90th percentile ($L$).
- Candidate Estimation: Uses $L$ as the new padding limit to obtain more precise counts.
- Bias Correction: Applies a mathematical update factor to correct the systematic under-estimation inherent in the sampling process.
SVSM (Set-Value itemSet Mining)
SVSM represents the first effective LDP protocol for finding frequent combinations of items (itemsets). It leverages the results from SVIM to intelligently predict which combinations are likely to be frequent, significantly narrowing the search space before performing measurements.
Key Insights and Privacy Amplification
A core theoretical contribution of this work is the discovery of the Privacy Amplification theorem. The authors proved that the act of sampling a single item from a set of size $\ell$ provides a natural privacy "bonus." This allows the protocol to utilize a higher internal privacy budget ($\epsilon'$) while maintaining the user's desired overall privacy guarantee ($\epsilon$).
As shown in the figure above, for a fixed overall privacy budget $\epsilon$, the internal budget $\epsilon'$ can be significantly larger, especially as the padding size $\ell$ increases. This higher internal budget translates directly to lower noise and higher accuracy. However, the authors also noted that this benefit is mechanism-dependent; it applies to Generalized Randomized Response (GRR) but not to Optimized Local Hash (OLH), leading to the development of an "Adaptive FO" that switches mechanisms based on the data domain.
Evaluation and Results
The protocols were rigorously tested on four large-scale datasets, including merchant transactions (POS, Online) and clickstream data (Kosarak). The results demonstrate a breakthrough in LDP data mining:
- Accuracy: On the POS dataset, SVIM correctly identified 45 frequent items, compared to only 12 by the previous state-of-the-art, LDPMiner.
- Variance: The estimation error for SVIM was frequently three orders of magnitude lower than existing methods.
- Itemset Discovery: SVSM achieved a 7x improvement in identifying top-10 frequent itemsets, solving a problem previously considered an open challenge in the LDP field.
Conclusion
By formalizing the PSFO framework and identifying the privacy amplification effect of sampling, this work provides a robust solution for mining frequent items and itemsets in set-valued data. SVIM and SVSM offer a significant leap in utility for privacy-preserving analytics, enabling organizations to derive meaningful trends from complex user data without compromising individual privacy.
Summary updated