Local differentially private fuzzy counting in stream data using probabilistic data structures

Privacy-preserving estimation of counts of items in streaming data finds applications in several real-world scenarios including word auto-correction and traffic management applications. Recent works of RAPPOR Erlingsson et al. (2014) and Apple's count-mean sketch (CMS) algorithm D. P. T. Apple, (2017) propose privacy preserving mechanisms for count estimation in large volumes of data using probabilistic data structures like counting Bloom filter and CMS. However, these existing methods fall short in providing a sound solution for real-time streaming data applications. Since the size of the data structure in these methods is not adaptive to the volume of the streaming data, the utility (accuracy of the count estimate) can suffer over time due to increased false positive rates. Further, the lookup operation needs to be highly efficient to answer count estimate queries in real-time. More importantly, the local Differential privacy mechanisms used in these approaches to provide privacy guarantees come at a large cost to utility (impacting the accuracy of count estimation). In this work, we propose a novel (local) Differentially private mechanism that provides high utility for the streaming data count estimation problem with similar or even lower privacy budgets while providing: a) fuzzy counting to report counts of related or similar items (for instance to account for typing errors and data variations), and b) improved querying efficiency to reduce the response time for real-time querying of counts. Our algorithm uses a combination of two probabilistic data structures Cuckoo filter and Bloom filter. We provide formal proofs for privacy and utility guarantees and present extensive experimental evaluation of our algorithm using real and synthetic English words datasets for both the exact and fuzzy counting scenarios. Our privacy preserving mechanism substantially outperforms the prior work in terms of lower querying time, significantly higher utility (accuracy of count estimation) under similar or lower privacy guarantees, at the cost of communication overhead.