Practical protocol for Yao's millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets

There are no files associated with this record.

Title Practical protocol for Yao's millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets
Author Amirbekyan, Artak; Estivill-Castro, Vladimir
Journal Name Knowledge and Information Systems
Year Published 2009
Place of publication United Kingdom
Publisher Springer
Abstract Finding the nearest k objects to a query object is a fundamental operation for many data mining algorithms. With the recent interest in privacy, it is not surprising that there is strong interest in k-NN queries to enable clustering, classification and outlier-detection tasks. However, previous approaches to privacy-preserving k-NN have been costly and can only be realistically applied to small data sets. In this paper, we provide efficient solutions for k-NN queries for vertically partitioned data. We provide the first solution for the L(inf) (or Chessboard) metric as well as detailed privacy-preserving computation of all other Minkowski metrics. We enable privacy-preserving L(inf) by providing a practical approach to the Yao's millionaire problem with more than two parties. This is based on a pragmatic and implementable solution to Yao's millionaire problem with shares. We also provide privacy-preserving algorithms for combinations of local metrics into a global metric that handles the large dimensionality and diversity of attributes common in vertically partitioned data. To manage very large data sets, we provide a privacy-preserving SASH (a very successful data structure for associative queries in high dimensions). Besides providing a theoretical analysis, we illustrate the efficiency of our approach with an empirical evaluation.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1007/s10115-009-0233-z
Volume 21
Issue Number 3
Page from 327
Page to 363
ISSN 0219-3116
Date Accessioned 2010-03-04
Date Available 2010-08-05T07:15:38Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Analysis of Algorithms and Complexity; Distributed Computing; Pattern Recognition and Data Mining
URI http://hdl.handle.net/10072/30120
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice