Privacy preserving outsourcing of association rule mining

Spurred by developments such as cloud computing, there has been considerable recent interest in the paradigmof datamining-as-service. A company (data owner) lacking in expertise or computational resources can outsource its mining needs to a third party service provider (server). However, both the items in the outsourced database and the patterns of items that can be mined from the database, are considered as the corporate privacy of the data owner. To protect the corporate privacy, the data owner transforms its data and ships it to the server. The server sends extracted patterns to the owner in response to the latters mining queries. The owner recovers the true patterns from the extracted patterns received. In this paper, we study the problem of outsourcing the association rule mining task within a corporate privacy-preserving framework. We propose an attack model based on background knowledge and devise two schemes, namely Frugal and RobFrugal , for privacy-preserving outsourced mining, based on the concept of k-anonymity. The protection against the privacy violation attack comes from ensuring that each transformed item (itemset) is indistinguishable, w.r.t. the attacker's background knowledge, from at least k-1 other transformed items (itemsets). We show that the owner can recover the true patterns as well as their support by maintaining a compact synopsis. Finally, we empirically demonstrate using comprehensive experiments on a real transaction database, that our techniques and ideas are effective, scalable, and protect privacy.