κ-Support Anonymity Based on Pseudo Taxonomy for Outsourcing of Frequent Itemset Mining

摘要

For any outsourcing service, privacy is a major concern. This paper focuses on outsourcing frequent itemset mining and examines the issue on how to protect privacy against the case where the attackers have precise knowledge on the supports of some items. We propose a new approach referred to as fc-support anonymity to protect each sensitive item with fc — 1 other items of similar support. To achieve fc-support anonymity, we introduce a pseudo taxonomy tree and have the third party mine the generalized frequent itemsets under the corresponding generalized association rules instead of association rules. The pseudo taxonomy is a construct to facilitate hiding of the original items, where each original item can map to either a leaf node or an internal node in the taxonomy tree. The rationale for this approach is that with a taxonomy tree, the fc nodes to satisfy the fc-support anonymity may be any fc nodes in the taxonomy tree with the appropriate supports. So this approach can provide more candidates for fc-support anonymity with limited fake items as only the leaf nodes, not the internal nodes, of the taxonomy tree need to appear in the transactions. Otherwise for the association rule mining, the fc nodes to satisfy the fc-support anonymity have to correspond to the leaf nodes in the taxonomy tree. This is far more restricted. The challenge is thus on how to generate the pseudo taxonomy tree to facilitate fc-support anonymity and to ensure the conservation of original frequent itemsets. The experimental results showed that our methods of fc-support anonymity can achieve very good privacy protection with moderate storage overhead.