When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery
Bo Jiang
Network and Distributed System Security (NDSS) Symposium 2026 · Day 1 · Privacy & Measurement
Local differential privacy (LDP) is a cornerstone of privacy-preserving data collection, used by companies like Google and Apple to gather statistics without trusting any central server. However, the standard **Count Mean Sketch (CMS)** approach uses fixed, deterministic parameters that are not optimized for real-world use cases. This talk from **TikTok** researchers presents a generalized CMS approach that tunes perturbation parameters based on the target query frequency range, achieving lower variance for queries of interest while simultaneously reducing communication costs by at least **50%**. The researchers also introduce an unknown item discovery protocol that uses a semi-honest auxiliary server to reduce the computational cost of discovering new, previously unseen items from cubic to **linear time**.
AI review
A mathematical optimization of local differential privacy parameters that improves the Count Mean Sketch protocol's utility and reduces communication costs. Clean theoretical work with practical implications for companies deploying LDP at scale, but zero relevance to security research, offensive techniques, or vulnerability analysis. This is a privacy/statistics paper at a security conference.