The Privacy of k-NN Retrieval for Horizontal Partitioned Data - New Methods and Applications

File Size Format
48368_1.pdf 251Kb Adobe PDF View
Title The Privacy of k-NN Retrieval for Horizontal Partitioned Data - New Methods and Applications
Author Amirbekyan, Artak; Estivill-Castro, Vladimir
Publication Title Database Technologies 2007 : Proceedings of the Eighteenth Australasian Database Conference (ADC2007)
Editor James Bailey and Alan Fekete
Year Published 2007
Place of publication Ballarat, Australia
Publisher Australian Computer Society
Abstract Recently, privacy issues have become important in clustering analysis, especially when data is horizontally partitioned over several parties. Associative queries are the core retrieval operation for many data mining algorithms, especially clustering and k-NN classification. The algorithms that effciently support k-NN queries are of special interest. We show how to adapt well-known data structures to the privacy preserving context and what is the overhead of this adaptation. We present an algorithm for k-NN in secure multiparty computation. This is based on presenting private computation of several metrics. As a result, we can offer three approaches to associative queries over horizontally partitioned data with progressively less security. We show privacy preserving algorithms for data structures that induce a partition on the space; such as KD-Trees. Our next preference is our Privacy Preserving SASH. However, we demonstrate that the most effective approach to achieve privacy is separate data structures for parties, where associative queries work separately, followed by secure combination to produce the overall output. This idea not only enhances security but also reduces communication cost between data holders. Our results and protocols also enable us to improve on previous approaches for k-NN classification
Peer Reviewed Yes
Published Yes
Publisher URI http://www.acs.org.au/
Alternative URI http://www.se.auckland.ac.nz/acsc07/
Copyright Statement Copyright 2007 Australian Computer Society Inc. The attached file is reproduced here in accordance with the copyright policy of the publisher. Use hypertext link for access to the conference website.
ISBN 1920682449
Conference name Eighteenth Australasian Database Conference (ADC 2007)
Location Ballarat, Australia
Date From 2007-01-30
Date To 2007-02-02
URI http://hdl.handle.net/10072/17248
Date Accessioned 2008-02-08
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Data Security
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice