Efficient Sanitization of Informative Association Rules

[[abstract]]Recent development in Privacy-Preserving Data Mining has proposed many efficient and practical techniques for hiding sensitive patterns or information from been discovered by data mining algorithms. In hiding association rules, current approaches require hidden rules or patterns to be given in advance. In addition, for Apriori algorithm based techniques [26], multiple scanning of the entire database is required. For direct sanitization of itemsets from transaction techniques [21], one scanning of each window in the database is processed independently. However, the accumulated information among windows is not considered. In this work, we propose an efficient one database scanning sanitization algorithm to sanitize informative association rules. For a given predicting item, an informative association rule set [16] is the smallest association rule set that makes the same prediction as the entire association rule set by confidence priority. A new data structure called pattern-inversion tree is proposed to store related information so that only one scan of database is required. The pre-process of finding these informative association rules can be integrated into the sanitization process. Numerical experiments show that the performance of the proposed algorithm is more efficient than previous algorithms with similar side effects. Running time complexity of the algorithm is presented and compared to similar algorithm with better complexity