AUTHENTICATED MULTISTEP NEAREST NEIGHBOR SEARCH


  AUTHENTICATED MULTISTEP.doc (Size: 329.5 KB / Downloads: 7)

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.

INTRODUCTION:

Authenticated multistep NN search for applications that require a proof of result correctness. Clients issue similarity queries to a provider. The latter returns the result set and additional verification information, based on which the client establishes that the result is indeed correct, i.e., it contains exactly the records of DB that satisfy the query conditions, and that these records indeed originate from their legitimate data source. A similar situation occurs for data replication, i.e., when a data owner stores DB at several servers. Clients issue their queries to the closest server, but they wish to be assured that the result is the same as if the queries were sent to the original source of DB. Notarization services have been proposed to safeguard against tampering in document databases.

PROPOSED TECHNIQUES:

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. 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. AMN, an adaptation of a multistep algorithm that is optimal in terms of DST computations. AMN requires transmissions of false hits. C-AMN, alleviates this problem through an elaborate scheme that reduces the size of false hits. We consider a distributed setting, where the database is horizontally partitioned over several servers. ID-AMN incrementally retrieves data, gradually eliminating servers that cannot contribute results.