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