Private Decayed Sum Estimation under Continual Observation

Details Private Decayed Sum Estimation under Continual Observation Private Decayed Sum Estimation under Continual Observation

2011-08-31

arxiv.org/abs/1108.6123v2

Computer Science

Data Structures and Algorithms

Scientific paper

In monitoring applications, recent data is more important than distant data. How does this affect privacy of data analysis? We study a general class of data analyses - computing predicate sums - with privacy. Formally, we study the problem of estimating predicate sums {\em privately}, for sliding windows (and other well-known decay models of data, i.e. exponential and polynomial decay). We extend the recently proposed continual privacy model of Dwork et al. We present algorithms for decayed sum which are $\eps$-differentially private, and are accurate. For window and exponential decay sums, our algorithms are accurate up to additive $1/\eps$ and polylog terms in the range of the computed function; for polynomial decay sums which are technically more challenging because partial solutions do not compose easily, our algorithms incur additional relative error. Further, we show lower bounds, tight within polylog factors and tight with respect to the dependence on the probability of error.

Affiliated with

Also associated with

No associations

Rating

Private Decayed Sum Estimation under Continual Observation 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 Private Decayed Sum Estimation under Continual Observation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Private Decayed Sum Estimation under Continual Observation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-625076