Answering differentially private queries for continual datasets release

Privacy preserving data release is a hot topic that attracts a lot of attentions in data mining, machine learning, and social network communities. Most studies on privacy preserving focus on static data releases; however, data are usually updated periodically. As a potential solution, differential privacy addresses continual data release by simplifying it into an event stream release problem. This approach overlooks the relationship between events, which is defined as coupled information in this paper. We argue that datasets cannot be simplified as an event stream due to the coupled information. In addition, the coupled information may reveal more private information than expected. This work proposes a privacy-preserving mechanism that explicitly identify the coupled information in continually released datasets. In stead of simplifying datasets to event streams, this mechanism considers the continual released datasets as coupled datasets based on the relationship between the same individual in different datasets, and the relationship between different individuals in the same dataset. We also propose the notion of coupled sensitivity for answering differentially private queries and develop an iterative based coupled continual release algorithm, called CCR, that answers these queries with a large set of differentially private results. Theoretical analysis proves the privacy of this method, and an extensive performance study shows that CCR outperforms traditional differential privacy mechanisms when answering a large set of queries.