Efficient Batch Query Answering Under Differential Privacy

Details Efficient Batch Query Answering Under Differential Privacy Efficient Batch Query Answering Under Differential Privacy

2011-03-07

arxiv.org/abs/1103.1367v1

Computer Science

Databases

6 figues, 22 pages

Scientific paper

Differential privacy is a rigorous privacy condition achieved by randomizing query answers. This paper develops efficient algorithms for answering multiple queries under differential privacy with low error. We pursue this goal by advancing a recent approach called the matrix mechanism, which generalizes standard differentially private mechanisms. This new mechanism works by first answering a different set of queries (a strategy) and then inferring the answers to the desired workload of queries. Although a few strategies are known to work well on specific workloads, finding the strategy which minimizes error on an arbitrary workload is intractable. We prove a new lower bound on the optimal error of this mechanism, and we propose an efficient algorithm that approaches this bound for a wide range of workloads.

Affiliated with

Also associated with

No associations

Rating

Efficient Batch Query Answering Under Differential Privacy 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 Efficient Batch Query Answering Under Differential Privacy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Batch Query Answering Under Differential Privacy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-81532