Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data
|
Data mining can extract important knowledge from large data collections—but sometimes these collections are split among various parties. Privacy concerns may prevent the parties from directly sharing the data and some types of information about the data. This paper addresses secure mining of association rules over horizontally partitioned data. The methods incorporate cryptographic techniques to minimize the information shared, while adding little overhead to the mining task.
[1] 1026 R. Agrawal and R. Srikant, Fast Algorithms for Mining Association Rules Proc. 20th Int'l Conf. Very Large Data Bases, pp. 487-499, 1994, available:http://www.vldb.org/dblp/db/conf/vldbvldb94-487.html .
[2] D. Cheung, J. Han, V. Ng, A. Fu, and Y. Fu, “A Fast Distributed Algorithm for Mining Association Rules,” Fourth Int'l Conf. Parallel and Distributed Information Systems, Dec. 1996.
[3] D.W. Cheung, V.T. Ng, W. Fu, and Y. Fu, “Efficient Mining Association Rules in Distributed Databases,” IEEE Trans. Knowledge and Data Eng., vol. 8, no. 6, pp. 911-922, Dec. 1996.
[4] R. Agrawal and R. Srikant, Privacy-Preserving Data Mining Proc. 2000 ACM SIGMOD Conf. Management of Data, pp. 439-450, 2000, available:.
[5] D. Agrawal and C.C. Aggarwal, On the Design and Quantification of Privacy Preserving Data Mining Algorithms Proc. 20th ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems, pp. 247-255, 2001, available:http://doi.acm.org/10.1145375551.375602.
[6] A. Evfimievski, R. Srikant, R. Agrawal, and J. Gehrke, Privacy Preserving Mining of Association Rules Proc. Eighth ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining, pp. 217-228, 2002, available:.
[7] S.J. Rizvi and J.R. Haritsa, Maintaining Data Privacy in Association Rule Mining Proc. 28th Int'l Conf. Very Large Data Bases, pp. 682-693, 2002, available:http://www.vldb.org/conf/2002S19P03.pdf.
[8] Y. Lindell and B. Pinkas, Privacy Preserving Data Mining Advances in Cryptology (CRYPTO 2000), pp. 36-54, 2000, available:http://link.springer.de/link/service/series/ 0558/bibs/188018800036.htm.
[9] O. Goldreich, Secure Multiparty Computation (working draft), Sept. 1998, available:http://www.wisdom.weizmann.ac.il/~odedpp.html .
[10] J. Vaidya and C. Clifton, Privacy Preserving Association Rule Mining in Vertically Partitioned Data Proc. Eighth ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining, pp. 639-644, 2002, available:.
[11] A.C. Yao, How to Generate and Exchange Secrets Proc. 27th IEEE Symp. Foundations of Computer Science, pp. 162-167, 1986.
[12] I. Ioannidis and A. Grama, An Efficient Protocol for Yao's Millionaires'Problem Proc. Hawaii Int'l Conf. System Sciences (HICSS-36), 2003.
[13] O. Goldreich, Encryption Schemes (working draft), Mar. 2003, available:http://www.wisdom.weizmann.ac.il/~oded/PSBook Frag enc.ps.
[14] R.L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems Comm. ACM, vol. 21, no. 2, pp. 120-126, 1978, available:.
[15] S.C. Pohlig and M.E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance IEEE Trans. Information Theory, vol. IT-24, pp. 106-110, 1978.
[16] M.K. Reiter and A.D. Rubin, Crowds: Anonymity for Web Transactions ACM Trans. Information and System Security, vol. 1, no. 1, pp. 66-92, Nov. 1998, available:.
[17] J.C. Benaloh, Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret Advances in Cryptography (CRYPTO86): Proc., A. Odlyzko, ed., pp. 251-260, 1986, available:http://spring erlink.metapress.comopenurl.asp?genre=article&issn=0302-9%743&volume=263&spage=251 .
[18] B. Chor and E. Kushilevitz, A Communication-Privacy Tradeoff for Modular Addition Information Processing Letters, vol. 45, no. 4, pp. 205-210, 1993.
[19] C. Clifton, M. Kantarcioglu, and J. Vaidya, Defining Privacy for Data Mining Proc. US Nat'l Science Foundation Workshop on Next Generation Data Mining, H. Kargupta, A. Joshi, and K. Sivakumar, eds., pp. 126-133, 2002.
[20] B.A. Huberman, M. Franklin, and T. Hogg, Enhancing Privacy and Trust in Electronic Communities Proc. First ACM Conf. Electronic Commerce (EC '99), pp. 78-86, 1999.
[21] J.C. Benaloh and M. de Mare, One-Way Accumulators: A Decentralized Alternative to Digital Signatures Advances in Cryptology - EUROCRYPT '93, Workshop Theory and Application of Cryptographic Techniques, pp. 274-285, 1993, available:http://springerlink.metapress.comopenurl.asp?genre=art cle&issn=0302-9%743&volume=765&spage=274 .
[22] W. Diffie and M.E. Hellman, New Directions in Cryptography IEEE Trans. Information Theory, vol. 22, pp. 644-654, 1976.
[23] T. ElGamal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms IEEE Trans. Information Theory, vol. 31, no. 4, pp. 469-472, 1985.
[24] A. Shamir, R.L. Rivest, and L.M. Adleman, Mental Poker Technical Memo MIT-LCS-TM-125, Laboratory for Computer Science, MIT, Feb. 1979.
Index Terms:
Data mining, security, privacy.
Citation:
Murat Kantarcioglu, Chris Clifton, "Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1026-1037, Sept. 2004, doi:10.1109/TKDE.2004.45
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb