Please use this identifier to cite or link to this item: https://doi.org/10.1109/TKDE.2010.157
Title: Authenticated multistep nearest neighbor search
Authors: Papadopoulos, S.
Wang, L.
Yang, Y.
Papadias, D.
Karras, P. 
Keywords: multistep nearest neighbors
Query authentication
similarity search
Issue Date: 2011
Source: Papadopoulos, S., Wang, L., Yang, Y., Papadias, D., Karras, P. (2011). Authenticated multistep nearest neighbor search. IEEE Transactions on Knowledge and Data Engineering 23 (5) : 641-654. ScholarBank@NUS Repository. https://doi.org/10.1109/TKDE.2010.157
Abstract: Multistep processing is commonly used for nearest neighbor (NN) and similarity search in applications involving high-dimensional data and/or costly distance computations. Today, many such applications require a proof of result correctness. In this setting, clients issue NN queries to a server that maintains a database signed by a trusted authority. The server returns the NN set along with supplementary information that permits result verification using the data set signature. An adaptation of the multistep NN algorithm incurs prohibitive network overhead due to the transmission of false hits, i.e., records that are not in the NN set, but are nevertheless necessary for its verification. In order to alleviate this problem, we present a novel technique that reduces the size of each false hit. Moreover, we generalize our solution for a distributed setting, where the database is horizontally partitioned over several servers. Finally, we demonstrate the effectiveness of the proposed solutions with real data sets of various dimensionalities. © 2006 IEEE.
Source Title: IEEE Transactions on Knowledge and Data Engineering
URI: http://scholarbank.nus.edu.sg/handle/10635/39531
ISSN: 10414347
DOI: 10.1109/TKDE.2010.157
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

7
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

1
checked on Dec 11, 2017

Page view(s)

61
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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