Top-k discovery under local differential privacy : an adaptive sampling approach

Abstract

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.