Distributed Private Heavy Hitters

Details Distributed Private Heavy Hitters Distributed Private Heavy Hitters

2012-02-22

arxiv.org/abs/1202.4910v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we give efficient algorithms and lower bounds for solving the heavy hitters problem while preserving differential privacy in the fully distributed local model. In this model, there are n parties, each of which possesses a single element from a universe of size N. The heavy hitters problem is to find the identity of the most common element shared amongst the n parties. In the local model, there is no trusted database administrator, and so the algorithm must interact with each of the $n$ parties separately, using a differentially private protocol. We give tight information-theoretic upper and lower bounds on the accuracy to which this problem can be solved in the local model (giving a separation between the local model and the more common centralized model of privacy), as well as computationally efficient algorithms even in the case where the data universe N may be exponentially large.

Affiliated with

Also associated with

No associations

Rating

Distributed Private Heavy Hitters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Private Heavy Hitters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Private Heavy Hitters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-415157