Abstract
Local differential privacy (LDP) has recently become a popular privacy-preserving data collection technique protecting users' privacy. The main problem of data stream collection under LDP is the poor utility due to multi-item collection from a very large domain. This paper proposes PrivSketch, a high-utility frequency estimation protocol taking advantage of sketches, suitable for private data stream collection. Combining the proposed background information and a decode-first collection-side workflow, PrivSketch improves the utility by reducing the errors introduced by the sketching algorithm and the privacy budget utilization when collecting multiple items. Our evaluation demonstrates that PrivSketch is 1-3 orders of magnitude better than the competitors in terms of utility in both frequency estimation and frequent item estimation, while being up to ~100x faster.
The Challenge of Private Data Streams
In the modern data ecosystem, tech giants like Apple and Google utilize Local Differential Privacy (LDP) to gather aggregate statistics—such as popular emojis or frequently visited websites—without compromising individual user privacy. In an LDP framework, users perturb their data locally before transmission, ensuring that the central collector never sees raw, sensitive information.
However, scaling LDP to data streams presents significant hurdles. When users contribute multiple items from massive domains (e.g., millions of unique URLs), existing protocols often fail due to two primary factors:
- Utility Degradation: The privacy budget ($\epsilon$) must be split across multiple items, leading to high noise levels that obscure the actual signal.
- Collision Errors: Sketch-based methods, used to handle large domains, suffer from "collision explosions" when noisy sketches from thousands of users are aggregated, compounding errors exponentially.
The PrivSketch Architecture
PrivSketch addresses these issues through a redesigned architecture that optimizes both the user-side encoding and the collector-side decoding process.
The protocol is built on three innovative pillars:
- Decode-First Workflow: Unlike traditional methods that aggregate all noisy sketches before decoding, PrivSketch decodes each user's perturbed sketch individually before aggregation. This prevents the compounding of collision noise during the summation phase.
- The Ordering Matrix: To improve accuracy without increasing the privacy budget, users send an "ordering matrix" ($O^{(i)}$). This matrix represents the relative rank of sketch counters. The authors prove that this background information does not violate LDP but allows the collector to perform the "Min" operation in Count-Min Sketches more accurately.
- Optimized Sampling: Instead of transmitting an entire noisy sketch, PrivSketch samples a single counter. This allows the user to allocate the entire privacy budget to one high-fidelity data point, significantly improving the signal-to-noise ratio.
Deep Dive: The Ordering Matrix
The ordering matrix is a key innovation for reducing sketch-induced errors. By providing the relative order of counters, the collector can better distinguish between actual item counts and noise without seeing the raw values.
Experimental Evaluation
The researchers benchmarked PrivSketch against state-of-the-art protocols (like Apple’s PCMS and PS-OLH) using both synthetic and real-world datasets, including clickstream data from news portals and massive AOL search logs containing 1.6 million distinct URLs.
Key Results
- Unmatched Accuracy: PrivSketch achieved 1 to 3 orders of magnitude lower Mean Squared Error (MSE) than competitors in frequency estimation tests.
- Exceptional Speed: The protocol is approximately 100x faster than PS-OLH and SVIM. For the massive AOL dataset, while other methods would require days of computation, PrivSketch processed the data efficiently.
- Scalability: While other LDP methods struggle as domain sizes grow, PrivSketch’s error rate remains remarkably stable, making it uniquely suited for large-scale web applications.
Conclusion
PrivSketch represents a significant leap forward in private data stream analysis. By rethinking the collector-side workflow and introducing the ordering matrix as a form of "safe" background information, it overcomes the traditional trade-offs between privacy, utility, and computational efficiency. While future work may focus on optimizing heavy-hitter discovery, PrivSketch currently stands as a highly robust solution for high-fidelity frequency estimation in the wild.
Summary updated