Fast Private Data Release Algorithms for Sparse Queries

Details Fast Private Data Release Algorithms for Sparse Queries Fast Private Data Release Algorithms for Sparse Queries

2011-11-29

arxiv.org/abs/1111.6842v1

Computer Science

Data Structures and Algorithms

Scientific paper

We revisit the problem of accurately answering large classes of statistical queries while preserving differential privacy. Previous approaches to this problem have either been very general but have not had run-time polynomial in the size of the database, have applied only to very limited classes of queries, or have relaxed the notion of worst-case error guarantees. In this paper we consider the large class of sparse queries, which take non-zero values on only polynomially many universe elements. We give efficient query release algorithms for this class, in both the interactive and the non-interactive setting. Our algorithms also achieve better accuracy bounds than previous general techniques do when applied to sparse queries: our bounds are independent of the universe size. In fact, even the runtime of our interactive mechanism is independent of the universe size, and so can be implemented in the "infinite universe" model in which no finite universe need be specified by the data curator.

Affiliated with

Also associated with

No associations

Rating

Fast Private Data Release Algorithms for Sparse Queries 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 Fast Private Data Release Algorithms for Sparse Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Private Data Release Algorithms for Sparse Queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-16586