TY - JOUR
T1 - Top-k Discovery Under Local Differential Privacy
T2 - An Adaptive Sampling Approach
AU - Du, Rong
AU - Ye, Qingqing
AU - Fu, Yue
AU - Hu, Haibo
AU - Huang, Kai
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2025
Y1 - 2025
N2 - 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.
AB - 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.
KW - Local differential privacy
KW - multi-armed bandit
KW - top-k Estimation
UR - https://www.scopus.com/pages/publications/105001072479
U2 - 10.1109/TDSC.2024.3471923
DO - 10.1109/TDSC.2024.3471923
M3 - 文章
AN - SCOPUS:105001072479
SN - 1545-5971
VL - 22
SP - 1763
EP - 1780
JO - IEEE Transactions on Dependable and Secure Computing
JF - IEEE Transactions on Dependable and Secure Computing
IS - 2
ER -