You are here

Privacy Preserving Nearest Neighbor Search

TitlePrivacy Preserving Nearest Neighbor Search
Publication TypeConference Paper
Year of Publication2006
AuthorsShaneck, M, Kim, Y, Kumar, V
Conference NameData Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on
Date PublishedDec
KeywordsClustering algorithms, Computer science, Conferences, cryptography, Data mining, data privacy, distributed computing, Kernel, kNN classification, LOF outlier detection, Medical diagnostic imaging, multiparty computation primitives, nearest neighbor search, Nearest neighbor searches, pattern clustering, privacy preservation, SNN clustering

Data mining is frequently obstructed by privacy concerns. In many cases data is distributed, and bringing the data together in one place for analysis is not possible due to privacy laws (e.g. HIPAA) or policies. Privacy preserving data mining techniques have been developed to address this issue by providing mechanisms to mine the data while giving certain privacy guarantees. In this work we address the issue of privacy preserving nearest neighbor search, which forms the kernel of many data mining applications. To this end, we present a novel algorithm based on secure multiparty computation primitives to compute the nearest neighbors of records in horizontally distributed data. We show how this algorithm can be used in three important data mining algorithms, namely LOF outlier detection, SNN clustering, and kNN classification

PDF icon PrivacyPreserving2006Shaneck.pdf125.41 KB