Mining Frequent Patterns with Differential Privacy

The mining of frequent patterns is a fundamental component in many data mining tasks. A considerable amount of research on this problem has led to a wide series of efficient and scalable al-gorithms for mining frequent patterns. However, releasing these patterns is posing concerns on the privacy of the users participating in the data. Indeed the information from the patterns can be linked with a large amount of data available from other sources creating opportunities for adversaries to break the individual privacy of the users and disclose sensitive information. In this proposal, we study the mining of frequent patterns in a privacy preserving setting. We first investigate the difference between sequential and itemset pat-terns, and second we extend the definition of patterns by consider-ing the absence and presence of noise in the data. This leads us in distinguishing the patterns between exact and noisy. For exact pat-terns, we describe two novel mining techniques that we previously developed. The first approach has been applied in a privacy pre-serving record linkage setting, where our solution is used to mine frequent patterns which are employed in a secure transformation procedure to link records that are similar. The second approach im-proves the mining utility results using a two-phase strategy which allows to effectively mine frequent substrings as well as prefixes patterns. For noisy patterns, first we formally define the patterns according to the type of noise and second we provide a set of po-tential applications that require the mining of these patterns. We conclude the paper by stating the challenges in this new setting and possible future research directions. 1