Further Study on Frequency Estimation under Local Differential Privacy

Local Differential Privacy (LDP) protects user privacy while collecting user data without the need for a trusted data collector. Nowadays, LDP protocols have been adopted and deployed by several major technology companies. A basic building block of LDP protocols is the frequency protocol, which estimates the frequency of each value in a specified domain. Although several frequency protocols have been proposed, all these protocols make compromises among the performances of accuracy, computation cost, and communication cost. In this paper, we introduce a precise and convenient equation to evaluate the accuracy of frequency protocols. We use it to analyze the advantages and disadvantages of existing protocols quantitatively. Based on the analysis, we address the shortcomings of these protocols and propose a new protocol, Random Wheel Spinner (RWS), which achieves optimal accuracy with low computation and communication costs simultaneously. Extensive experiments on both synthetic and real-world datasets demonstrate the advantages of our proposed protocols.