跳到主要导航 跳到搜索 跳到主要内容

Top-k Discovery Under Local Differential Privacy: An Adaptive Sampling Approach

  • Rong Du
  • , Qingqing Ye*
  • , Yue Fu
  • , Haibo Hu
  • , Kai Huang
  • *此作品的通讯作者
  • Hong Kong Polytechnic University
  • Macau University of Science and Technology

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

Local differential privacy (LDP) is a promising pri vacy model for data collection that protects sensitive information of individuals. However, applying LDP to top-k estimation in set valued data (e.g., identifying most frequent k items) may yield poor results for small and sparse datasets due to high sensitivity and heavy perturbation. To address this, we propose an adap tive approach that frames the problem as a multi-armed bandit (MAB)problem,inwhichthedecision-maker selects actions based on information collected from previous rounds to maximize the total reward over time. Inspired by this, we present two adaptive samplingschemes based on MAB:ARBS for identifying top-k items and ARBSF for both top-k item discovery and frequency estimation on these items. Furthermore, to address the potential long delay of multi-round collection, we propose an optimization technique to reduce the time complexity. Both theoretical and empirical results showthat our adaptive sampling schemes significantly outperform existing alternatives.

源语言英语
页(从-至)1763-1780
页数18
期刊IEEE Transactions on Dependable and Secure Computing
卷22
期2
DOI
出版状态已出版 - 2025
已对外发布是

学术指纹

探究 'Top-k Discovery Under Local Differential Privacy: An Adaptive Sampling Approach' 的科研主题。它们共同构成独一无二的学术指纹。

引用此