A Border-Based Approach for Hiding Sensitive Frequent Itemsets

Published 5 January 2006

Xingzhi Sun, Philip S. Yu

DOI10.1109/icdm.2005.2

Citations131

TL;DR

This paper proposes a border-based approach to efficiently evaluate the impact of any modification to the database during the hiding process to preserve the non-sensitive frequent itemsets.

Abstract

Sharing data among organizations often leads to mutual benefit. Recent technology in data mining has enabled efficient extraction of knowledge from large databases. This, however, increases risks of disclosing the sensitive knowledge when the database is released to other parties. To address this privacy issue, one may sanitize the original database so that the sensitive knowledge is hidden. The challenge is to minimize the side effect on the quality of the sanitized database so that nonsensitive knowledge can still be mined. In this paper, we study such a problem in the context of hiding sensitive frequent itemsets by judiciously modifying the transactions in the database. To preserve the non-sensitive frequent itemsets, we propose a border-based approach to efficiently evaluate the impact of any modification to the database during the hiding process. The quality of database can be well maintained by greedily selecting the modifications with minimal side effect. Experiments results are also reported to show the effectiveness of the proposed approach.

Keywords

Computer Science

Fast algorithms for mining association rules

10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant

Data Mining and Knowledge DiscoveryLevelwise Search and Borders of Theories in Knowledge Discovery

865 Citations1997Heikki Mannila, Hannu Toivonen

The concept of the border of a theory, a notion that turns out to be surprisingly powerful in analyzing the algorithm, is introduced and strong connections between the verification problem and the hypergraph transversal problem are shown.

ACM SIGMOD RecordState-of-the-art in privacy preserving data mining

813 Citations2004Vassilios S. Verykios, Elisa Bertino +4 more

An overview of the new and rapidly emerging research area of privacy preserving data mining is provided, and a classification hierarchy that sets the basis for analyzing the work which has been performed in this context is proposed.

IEEE Transactions on Knowledge and Data EngineeringAssociation rule hiding

522 Citations2004Vassilios S. Verykios, Ahmed K. Elmagarmid +3 more

This work investigates confidentiality issues of a broad category of rules, the association rules, and presents three strategies and five algorithms for hiding a group of associationrules, which is characterized as sensitive.

Disclosure limitation of sensitive rules

428 Citations2003Mikhail J. Atallah, Elisa Bertino +3 more

This paper attempted to selectively hide some frequent itemsets from large databases with as little as possible impact on other non-sensitive frequent itemets.

ACM SIGMOD RecordUsing unknowns to prevent discovery of association rules

339 Citations2001Yücel Saygın, Vassilios S. Verykios +1 more

This work introduces a method for selectively removing individual values from a database to prevent the discovery of a set of rules, while preserving the data for other applications.

Lecture notes in computer scienceHiding Association Rules by Using Confidence and Support

309 Citations2001Elena Dasseni, Vassilios S. Verykios +2 more

In this paper, confidentiality issues of a broad category of rules, which are called association rules, are investigated, if the disclosure risk of some of these rules are above a certain privacy threshold, those rules must be characterized as sensitive.

Privacy preserving frequent itemset mining

286 Citations2002Stanley Robson de Medeiros Oliveira, Osmar R. Zai͏̈ane

This paper proposes a new framework for enforcing privacy in mining frequent itemsets, and combines techniques for efficiently hiding restrictive patterns: a transaction retrieval engine relying on an inverted file and Boolean queries; and a set of algorithms to "sanitize" a database.

SECURITY AND PRIVACY IMPLICATIONS OF DATA MINING

265 Citations1996Chris Clifton, Donald G. Marks

This position paper discusses possible problems and solutions in data mining, and outlines ideas for further research in this area.

Protecting sensitive knowledge by data sanitization

198 Citations2004Stanley Robson de Medeiros Oliveira, Osmar R. Zaı̈ane

A new, efficient one-scan algorithm is introduced that meets privacy protection and accuracy in association rule mining, without putting at risk the effectiveness of the data mining per se.