On differentially private mechanisms for count-range queries and their applications.

摘要

As a result of the ever increasing ability to collect data, the amount of data available has exploded in recent years, which has sparked the coming era of "big data.'' Sophisticated analysis of the data at ever finer granularity has discovered hidden knowledge and produced economic value in a variety of domains. Meanwhile, individuals are also beginning to pay attention to the privacy implications brought up by such analysis, which might possibly reveal personal information. This problem is further compounded by the fact that we may not even know what data the individuals would like to protect nor what background information might be possessed by an adversary. Perhaps for the fear of privacy breaches, more and more people are becoming reluctant to contribute their data, hampering the data from being fully utilized. These compounding factors are exactly the ones addressed by differential privacy, which, intuitively, guarantees that the presence of an individual's data in a dataset does not reveal much about that individual. This dissertation develops the techniques to guarantee differential privacy for count-range queries, and then extends our techniques to various applications of count-range queries.;This dissertation first studies the optimal differentially private mechanisms for count-range queries. A count-range query is a Boolean query deciding whether or not the number of tuples in a database satisfying a given predicate is within a specified range, which is a simple form of the "having'' clause in SQL. We propose a differentially private mechanism for a single user which maximizes her utility. However, when considering the problem of serving multiple users, we prove that there is no differentially private mechanism that guarantees optimal utility for each user. On a positive note, we prove that such mechanism exists for a sub-class of the count-range queries. In the second part of the dissertation we investigate the problem of guaranteeing differential privacy for frequent itemset mining, which can be viewed as a sequence of count-range queries. We propose a differentially private frequent itemset mining algorithm which significantly improves the quality of the results on benchmark datasets over previous algorithms. Finally, we consider the problem of guaranteeing differential privacy in inductive logic programming. To the best of our knowledge, our work is the first to investigate the privacy issues in such a context. Although in general we show that it is very hard to simultaneously guarantee differential privacy and produce results of high quality, our experimental results show that our differentially private algorithm is able to produce accurate results when the size of the training data is large or the search space is small.