Privacy preserving distributed DBSCAN clustering

ABSTRACT

DBSCAN is a well-known density-based clustering algorithm which offers advantages for finding clusters of arbitrary shapes compared to partitioning and hierarchical clustering methods. However, there are few papers studying the DBSCAN algorithm under the privacy preserving distributed data mining model, in which the data is distributed between two or more parties, and the parties cooperate to obtain the clustering results without revealing the data at the individual parties. In this paper, we address the problem of two-party privacy preserving DBSCAN clustering. We first propose two protocols for privacy preserving DBSCAN clustering over horizontally and vertically partitioned data respectively and then extend them to arbitrarily partitioned data. We also provide analysis of the performance and proof of privacy of our solution.

References

1. R. Agrawal and R. Srikant. Privacy-preserving data mining. In SIGMOD Conference, pages 439--450, 2000.
2. M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the clustering structure. In SIGMOD Conference, pages 49--60, 1999.
3. R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively secure multi-party computation. In STOC, pages 639--648, 1996.
4. W. Du and Z. Zhan. Using randomized response techniques for privacy-preserving data mining. In KDD, pages 505--510, 2003.
5. M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, pages 226--231, 1996.
6. O. Goldreich. Foundations of cryptography: Basic applications, volume 2. Cambridge Univ Pr, 2004.
7. A. Hinneburg and D. A. Keim. An efficient approach to clustering in large multimedia databases with noise. In KDD, pages 58--65, 1998.
8. G. Jagannathan and R. N. Wright. Privacy-preserving distributed k-means clustering over arbitrarily partitioned data. In KDD, pages 593--599, 2005.
9. K. A. Kumar and C. P. Rangan. Privacy preserving dbscan algorithm for clustering. In ADMA, pages 57--68, 2007.
10. Y. Lindell and B. Pinkas. Privacy preserving data mining. J. Cryptology, 15(3):177--206, 2002.
11. R. T. Ng and J. Han. Efficient and effective clustering methods for spatial data mining. In VLDB, pages 144--155, 1994.
12. R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy. The effectiveness of lloyd-type methods for the k-means problem. In FOCS, pages 165--176, 2006.
13. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pages 223--238, 1999.
14. J. Vaidya and C. Clifton. Privacy-preserving κ-means clustering over vertically partitioned data. In KDD, pages 206--215, 2003.
15. A. C.-C. Yao. Protocols for secure computations (extended abstract). In FOCS, pages 160--164, 1982.
16. A. C.-C. Yao. How to generate and exchange secrets (extended abstract). In FOCS, pages 162--167, 1986.