Top-k Discovery Under Local Differential Privacy: An Adaptive Sampling Approach
Rong Du, Qingqing Ye, Yue Fu, Haibo Hu, Kai Jian Huang · IEEE Transactions on Dependable and Secure Computing · 2024
Local differential privacy (LDP) is a promising privacy 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 adaptive approach that frames the problem as a multi-armed bandit (MAB) problem, in which the decision-maker selects actions based on information collected from previous rounds to maximize the total reward over time. Inspired by this, we present two adaptive sampling schemes based on MAB:ARBSfor identifying top-$k$items andARBSFfor 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 show that our adaptive sampling schemes significantly outperform existing alternatives.