Heavy hitter estimation over set-valued data with local differential privacy

Zhan Qin, Yin Yang, Ting Yu, Issa Khalil, Xiaokui Xiao, Kui Ren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

245 Citations (Scopus)


In local differential privacy (LDP), each user perturbs her data locally before sending the noisy data to a data collector. The latter then analyzes the data to obtain useful statistics. Unlike the setting of centralized differential privacy, in LDP the data collector never gains access to the exact values of sensitive data, which protects not only the privacy of data contributors but also the collector itself against the risk of potential data leakage. Existing LDP solutions in the literature are mostly limited to the case that each user possesses a tuple of numeric or categorical values, and the data collector computes basic statistics such as counts or mean values. To the best of our knowledge, no existing work tackles more complex data mining tasks such as heavy hitter discovery over set-valued data. In this paper, we present a systematic study of heavy hitter mining under LDP. We first review existing solutions, extend them to the heavy hitter estimation, and explain why their effectiveness is limited. We then propose LDPMiner, a two-phase mechanism for obtaining accurate heavy hitters with LDP. The main idea is to first gather a candidate set of heavy hitters using a portion of the privacy budget, and focus the remaining budget on refining the candidate set in a second phase, which is much more efficient budget-wise than obtaining the heavy hitters directly from the whole dataset. We provide both in-depth theoretical analysis and extensive experiments to compare LDPMiner against adaptations of previous solutions. The results show that LDPMiner significantly improves over existing methods. More importantly, LDPMiner successfully identifies the majority true heavy hitters in practical settings.

Original languageEnglish
Title of host publicationCCS 2016 - Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)9781450341394
Publication statusPublished - Oct 24 2016
Externally publishedYes
Event23rd ACM Conference on Computer and Communications Security, CCS 2016 - Vienna, Austria
Duration: Oct 24 2016Oct 28 2016

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Other23rd ACM Conference on Computer and Communications Security, CCS 2016


  • Heavy hitter
  • Local differential privacy

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Heavy hitter estimation over set-valued data with local differential privacy'. Together they form a unique fingerprint.

Cite this