Differential privacy with graph based query set

As the technology and science has been improved, our daily life has changed. Especially, with the invention and improvement of computer at the 20th century, we can say that one of the most important thing that affects human life is computer science. According to Szalay and Gray, Computational Science is the new branch of most disciplines. However, empirical science was mainly a thousand years ago. After that, in the past five hundred years, theoretical science had been a part for almost every discipline. But now, most disciplines have empirical and theoretical parts. Moreover, in the past fifty years, computational branch has been another part for most disciplines. To give an example and clarify this, we can consider Physics. Physics has different branches; empirical Physics, theoretical Physics and computational Physics. And due to the Computational Science, scientist have to deal with a huge amount of data which is from new scientific instruments, simulations, online data and Internet. So, because of information management by computational science, computer science challenges have been shown up. There is a popular word which mentions that people are living in the information age. If we understand what data mining is, that word is not correct. Human are living in the data age actually. As it is mentioned, there is a great amount of data that is collected each every day and will be. Some people take data mining as a synonym for knowledge discovery from data, whereas some take it as just a step in the knowledge discovery process. These steps are data cleaning, data integration, data selection, data transformation, data mining, pattern evaluation and knowledge presentation. Data cleaning, data integration, data selection and data transformation are considered as preprocessing for data mining. And at the mining step some intelligent methods are applied to find patterns. Then with evaluation where interesting patterns due to interesting measures are represented. These are the steps to turn data into knowledge. It is a common approach that data are published for analysis. However, there is a privacy risks behind of sharing data. This privacy risk and possible disadvantage is the disclosure of sensitive information of individual. There is an area to prevent this risk which is called Privacy Preserving Data Mining. According to the description of Evfimievski and Grandison, this area tries to safeguard sensitive information from unsolicited or unsanctioned disclosure. To mention some studies of the Privacy Preserving Data Mining area, K-Anonymity, L-Diversity, T-Closeness has been published. K-Anonymity is a method which considers the quasi-identifiers, L-Diversity is a technique beyond K-Anonymity which considers diversity of sensitive data. And T-Closeness is another method beyond both K-Anonymity and L-Diversity. With T-Closeness method, it is aimed that the distribution of sensitive data in a group should be close to all data. Differential Privacy is a protection mechanism by Dwork. According to Dwork, there is no absolute guarantee by statistical database security, where semantic security in cryptography can guarantee to individuals. From a semantically secure cryptosystem, we can not gain any information about text-plain by cipher-text which can not be learned without seeing it. But Dwork proved that, same definition is not possible due to the auxiliary information. For example, supposing an attacker who knows an individual's height is 2 inches shorter than the average height of women in a country. And the database gives the information of the average height of women in the individuals' country. Then the attacker can exactly know the height of the individual. So there is always some risk for sensitive data for any statistical database. Moreover, there is two privacy mechanism models. One is non-interactive and the other one is interactive. With the non-interactive model, the data which has sensitive information is sanitized before it is published and shared. K-Anonymity is an example for this type of model. On the other hand, with interactive model, a trusted data collector provides an interface so that the interface users can pose queries and get the possible perturbed answers. Differential privacy is an example to interactive models. In this study, an approach to achieve the differential privacy is studied and explained. This model is fit for SQL which is very common in information technologies. With the approach and method only some statistical queries are considered to be answered with a provided interface. These statistical queries can have some aggregate functions which are COUNT, SUM, MIN and MAX. However, as an aggregate function COUNT is mainly considered and explained in this study. As the step for Differential Privacy, computation the sensitivity of a query set is NP-hard. But in the study, an approach to calculate the sensitivity of the query set is explained. So the solution is that building region-intersection graph for non ignored queries. After the intersections are measured, a graph is generated where each every node represents a query, and edges between nodes represents intersection of regions. Then it is showed that computation of the sensitivity of the query set is equivalent to bounding the sensitivity from above. After the sensitivity of the query set is found, Laplace noise is added to the each every non ignored query. To add the Laplace noise, there is two magnitude; the sensitivity of the query set and privacy budget ɛ. Then the users of the interface get the possibly perturbed answers and with the model Differential Privacy is provided for only statistical queries which fits the model. Moreover, it is possible to use this model for data analysis techniques. The model fits for some data analysis techniques because in order to apply the technique, the queries can be generated based on the model in this study. Although there is a lot of data analysis models fits with the model, there is some implemented and mentioned ones; Feature Selection with entropy, Correlation Analysis by chi-square test and Classification with Naïve Bayes Classifiers. All of these three data analysis techniques can be applied with SQL queries which fits the model explained. So, it is possible to analyze the data while protecting the sensitive information of individuals. Feature Selection is the process to calculate the top-k attributes with the lowest entropy. So that, the lowest entropy offers the highest information gain. The top-k attributes can be used to generate decision trees. Correlation Analysis is for analysis the correlation between the attributes of a table. In the study, Chi-square test is used to calculate the correlation between attributes. Naïve Bayesian Classifiers which are statistical, tries to find out the probabilities for a given tuple the belonging class. For example, according to a training data set, the belonging class probabilities of a tuple are found and decision is made.