DDRM: A Continual Frequency Estimation Mechanism with Local Differential Privacy

Qiao Xue, Qingqing Ye, Haibo Hu, Youwen Zhu, Jian Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review


Many applications rely on continual data collection to provide real-time information services, e.g., real-time road traffic forecasts. However, the collection of original data brings risks to user privacy. Recently, local differential privacy (LDP) has emerged as a private data collection framework for mass population. However, for continual data collection, existing LDP schemes, e.g., those employing the memoization technique, are known to have privacy leakage on data change points over time. In this paper, we propose a new scheme with stronger privacy guarantee for continual frequency estimation under LDP, namely, Dynamic Difference Report Mechanism (DDRM). In DDRM, we introduce difference trees to capture the data changes over time, which well addresses possible privacy leakage on data change points. As for the utility enhancement, DDRM exploits the common case of no data change in time series and thereby suppresses the consumption of privacy budget in such cases. Meanwhile, an optimal privacy budget allocation scheme is proposed to encourage users to report more data for better estimation accuracy. By both theoretical analysis and experimental evaluations, we show DDRM achieves highly accurate frequency estimation in real time.
Original languageEnglish
Article number9782510
Pages (from-to)1-14
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Publication statusAccepted/In press - May 2022


Dive into the research topics of 'DDRM: A Continual Frequency Estimation Mechanism with Local Differential Privacy'. Together they form a unique fingerprint.

Cite this