PrivKVM*: Revisiting Key-Value Statistics Estimation with Local Differential Privacy

Qingqing Ye, Haibo Hu, Xiaofeng Meng, Huadi Zheng, Kai Huang, Chengfang Fang, Jie Shi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)


A key factor in big data analytics and artificial intelligence is the collection of user data from a large population. However, the collection of user data comes at the price of privacy risks, not only for users but also for businesses who are vulnerable to internal and external data breaches. To address privacy issues, local differential privacy (LDP) has been proposed to enable an untrusted collector to obtain accurate statistical estimation on sensitive user data (e.g., location, health, and financial data) without actually accessing the true records. As key-value data is an extremely popular NoSQL data model, there are a few works in the literature that study LDP-based statistical estimation on key-value data. However, these works have some major limitations, including supporting small key space only, fixed key collection range, difficulty in choosing an appropriate padding length, and high communication cost. In this paper, we propose a two-phase mechanism PrivKVM* as an optimized and highly-complete solution to LDP-based key-value data collection and statistics estimation. We verify its correctness and effectiveness through rigorous theoretical analysis and extensive experimental results.
Original languageEnglish
Article number9524509
JournalIEEE Transactions on Dependable and Secure Computing
Publication statusAccepted/In press - Aug 2021


  • Data collection
  • Differential privacy
  • Estimation
  • Frequency estimation
  • Histograms
  • Key-value data
  • Perturbation methods
  • Privacy
  • histogram
  • local differential privacy
  • privacy-preserving data collection
  • statistics estimation

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'PrivKVM*: Revisiting Key-Value Statistics Estimation with Local Differential Privacy'. Together they form a unique fingerprint.

Cite this