|
ABSTRACT
We present a framework for mining association rules from transactions consisting of categorical items where the data has been randomized to preserve privacy of individual transactions. While it is feasible to recover association rules and preserve privacy using a straightforward "uniform" randomization, the discovered rules can unfortunately be exploited to find privacy breaches. We analyze the nature of privacy breaches and propose a class of randomization operators that are much more effective than uniform randomization in limiting the breaches. We derive formulae for an unbiased support estimator and its variance, which allow us to recover itemset supports from randomized datasets, and show how to incorporate these formulae into mining algorithms. Finally, we present experimental results that validate the algorithm by applying it on real datasets.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
 |
2
|
|
 |
3
|
|
 |
4
|
Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
|
| |
5
|
Rakesh Agrawal , Hiekki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
|
| |
6
|
R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. Research Report RJ 9839, IBM Almaden Research Center, San Jose, California, June 1994.
|
 |
7
|
|
 |
8
|
|
| |
9
|
L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, 1984.
|
| |
10
|
Business Week. Privacy on the Net, March 2000.
|
| |
11
|
C. Clifton and D. Marks. Security and privacy implications of data mining. In ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, pages 15--19, May 1996.
|
 |
12
|
|
| |
13
|
L. Cranor, J. Reagle, and M. Ackerman. Beyond concern: Understanding net users' attitudes about online privacy. Technical Report TR 99.4.3, AT&T Labs--Research, April 1999.
|
 |
14
|
|
| |
15
|
The Economist. The End of Privacy, May 1999.
|
| |
16
|
|
| |
17
|
European Union. Directive on Privacy Protection, October 1998.
|
| |
18
|
|
| |
19
|
|
| |
20
|
Office of the Information and Privacy Commissioner, Ontario. Data Mining: Staking a Claim on Your Privacy, January 1998.
|
| |
21
|
|
| |
22
|
|
| |
23
|
K. Thearling. Data mining and privacy: A conflict in making. DS*, March 1998.
|
| |
24
|
Time. The Death of Privacy, August 1997.
|
 |
25
|
|
| |
26
|
S. Warner. Randomized response: A survey technique for eliminating evasive answer bias. J. Am. Stat. Assoc., 60(309):63--69, March 1965.
|
| |
27
|
A. Westin. E-commerce and privacy: What net users want. Technical report, Louis Harris & Associates, June 1998.
|
| |
28
|
A. Westin. Privacy concerns & consumer choice. Technical report, Louis Harris & Associates, Dec. 1998.
|
| |
29
|
A. Westin. Freebies and privacy: What net users think. Technical report, Opinion Research Corporation, July 1999.
|
CITED BY 98
|
|
W. K. Wong , David W. Cheung , Edward Hung , Ben Kao , Nikos Mamoulis, Security in outsourcing of association rule mining, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Claus Boyens , Oliver Günther , Maximilian Teltzrow, Privacy conflicts in CRM services for online shops: a case study, Proceedings of the IEEE international conference on Privacy, security and data mining, p.27-35, December 01, 2002, Maebashi City, Japan
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dan Frankowski , Dan Cosley , Shilad Sen , Loren Terveen , John Riedl, You are what you say: privacy risks of public mentions, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
|
|
|
Sheng Zhang , James Ford , Fillia Makedon, A privacy-preserving collaborative filtering scheme with two-way communication, Proceedings of the 7th ACM conference on Electronic commerce, p.316-323, June 11-15, 2006, Ann Arbor, Michigan, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yabo Xu , Ke Wang , Ada Wai-Chee Fu , Philip S. Yu, Anonymizing transaction databases for publication, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wai Kit Wong , David Wai-lok Cheung , Ben Kao , Nikos Mamoulis, Secure kNN computation on encrypted databases, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
I.
Computing Methodologies
I.1
SYMBOLIC AND ALGEBRAIC MANIPULATION
I.1.2
Algorithms
Subjects:
Analysis of algorithms
Additional Classification:
H.
Information Systems
H.2
DATABASE MANAGEMENT
H.2.8
Database applications
Subjects:
Data mining
I.
Computing Methodologies
I.2
ARTIFICIAL INTELLIGENCE
I.2.3
Deduction and Theorem Proving
Subjects:
Deduction (e.g., natural, rule-based)
K.
Computing Milieux
K.6
MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
K.6.5
Security and Protection (D.4.6, K.4.2)
Subjects:
Unauthorized access (e.g., hacking, phreaking)
General Terms:
Design,
Experimentation,
Measurement,
Performance,
Reliability,
Security
|