EUVIMEDEUVIMED entdecken
Crossref

Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory

Xiaochen Li, Weiran Liu, Jian Lou, Yuan Hong, Lei Zhang, Zhan Qin, Kui Ren

Proceedings of the ACM on Management of Data · 12.03.2024 · 2 (1) · 1-27

DOI: 10.1145/3639285 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 26.03.2024. Verfasst von Xiaochen Li und 6 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 65 Literaturangaben. Gefördert von: The Major Programs of the National Social Science Foundation of China under Grant, The National Key Research and Development Program of China under Grant, The National Science Foundation under Grants.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Top-k frequent items detection is a fundamental task in data stream mining. Many promising solutions are proposed to improve memory efficiency while still maintaining high accuracy for detecting the Top-k items. Despite the memory efficiency concern, the users could suffer from privacy loss if participating in the task without proper protection, since their contributed local data streams may continually leak sensitive individual information. However, most existing works solely focus on addressing either the memory-efficiency problem or the privacy concerns but seldom jointly, which cannot achieve a satisfactory tradeoff between memory efficiency, privacy protection, and detection accuracy. In this paper, we present a novel framework HG-LDP to achieve accurate Top-k item detection at bounded memory expense, while providing rigorous local differential privacy (LDP) protection. Specifically, we identify two key challenges naturally arising in the task, which reveal that directly applying existing LDP techniques will lead to an inferior "accuracy-privacy-memory efficiency" tradeoff. Therefore, we instantiate three advanced schemes under the framework by designing novel LDP randomization methods, which address the hurdles caused by the large size of the item domain and by the limited space of the memory. We conduct comprehensive experiments on both synthetic and real-world datasets to show that the proposed advanced schemes achieve a superior "accuracy-privacy-memory efficiency" tradeoff, saving 2300× memory over baseline methods when the item domain size is 41,270. Our code is anonymously open-sourced via the link.

Förderung

  • The Major Programs of the National Social Science Foundation of China under Grant
  • The National Key Research and Development Program of China under Grant
  • The National Science Foundation under Grants
  • The National Natural Science Foundation of China under Grant

Zitieren

APA

Li, X., Liu, W., Lou, J., Hong, Y., Zhang, L., Qin, Z., & Ren, K. (2024). Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory. Proceedings of the ACM on Management of Data, 2(1), 1-27. https://doi.org/10.1145/3639285

Vancouver

Li X, Liu W, Lou J, Hong Y, Zhang L, Qin Z, et al. Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory. Proceedings of the ACM on Management of Data. 2024;2(1):1-27. doi:10.1145/3639285

BibTeX
@article{Li2024,
  author = {Li, Xiaochen and Liu, Weiran and Lou, Jian and Hong, Yuan and Zhang, Lei and Qin, Zhan and Ren, Kui},
  title = {Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {1},
  pages = {1--27},
  doi = {10.1145/3639285}
}
Kostenlos starten →