Discrete Distribution Estimation with Local Differential Privacy: A Comparative Analysis

Local differential privacy is a promising privacy-preserving model for\nstatistical aggregation of user data that prevents user privacy leakage from\nthe data aggregator. This paper focuses on the problem of estimating the\ndistribution of discrete user values with Local differential privacy. We review\nand present a comparative analysis on the performance of the existing discrete\ndistribution estimation algorithms in terms of their accuracy on benchmark\ndatasets. Our evaluation benchmarks include real-world and synthetic datasets\nof categorical individual values with the number of individuals from hundreds\nto millions and the domain size up to a few hundreds of values. The\nexperimental results show that the Basic RAPPOR algorithm generally performs\nbest for the benchmark datasets in the high privacy regime while the k-RR\nalgorithm often gives the best estimation in the low privacy regime. In the\nmedium privacy regime, the performance of the k-RR, the k-subset, and the HR\nalgorithms are fairly competitive with each other and generally better than the\nperformance of the Basic RAPPOR and the CMS algorithms.\n