Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/42159
Title: Authenticating kNN query results in data publishing
Authors: Cheng, W.
Tan, K.-L. 
Issue Date: 2007
Source: Cheng, W.,Tan, K.-L. (2007). Authenticating kNN query results in data publishing. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4721 LNCS : 47-63. ScholarBank@NUS Repository.
Abstract: In data publishing model, data owners engage third-party data publishers to manage their data and process queries on their behalf. As the publishers may be untrusted or susceptible to attacks, it could produce incorrect query results. In this paper, we extend the signaturebased mechanism for users to verify that their answers for k nearest neighbors queries on a multidimensional dataset are complete (i.e. no qualifying data points are omitted), authentic (i.e. no answer points are tampered) and minimal (i.e. no non-answer points are returned in the plain). Essentially, our scheme returns k answer points in the plain, and a set of (p̃, g)-pairs, where p̃ is the digest of a non-answer point p in the dataset used to facilitate the signature chaining mechanism to verify the authenticity of the answer points, and q is a reference point (not in the dataset) used to verify that p is indeed further away from the query point than the kth nearest point. We study two instantiations of the approach - one based on the native data space using space partitioning method (a.k.a. R-tree) and the other based on the metric space using iDistance. We conducted an experimental study, and report our findings here. © Springer-Verlag Berlin Heidelberg 2007.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/42159
ISBN: 9783540752479
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

47
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.