Confirmation Sampling for Exact Nearest Neighbor Search

Tobias Lybecker Christiani, Rasmus Pagh, Mikkel Thorup

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstract

Locality-sensitive hashing (LSH), introduced by Indyk and Motwani in STOC ’98, has been an extremely influential framework for nearest neighbor search in high-dimensional data sets. While theoretical work has focused on the approximate nearest neighbor problem, in practice LSH data structures with suitably chosen parameters are used to solve the exact nearest neighbor problem (with some error probability). Sublinear query time is often possible in practice even for exact nearest neighbor search, intuitively because the nearest neighbor tends to be significantly closer than other data points. However, theory offers little advice on how to choose LSH parameters outside of pre-specified worst-case settings.

We introduce the technique of confirmation sampling for solving the exact nearest neighbor problem using LSH. First, we give a general reduction that transforms a sequence of data structures that each find the nearest neighbor with a small, unknown probability, into a data structure that returns the nearest neighbor with probability 1−δ , using as few queries as possible. Second, we present a new query algorithm for the LSH Forest data structure with L trees that is able to return the exact nearest neighbor of a query point within the same time bound as an LSH Forest of Ω(L) trees with internal parameters specifically tuned to the query and data.
OriginalsprogEngelsk
TitelSISAP 2020: Similarity Search and Applications
ForlagSpringer
Publikationsdato2020
Sider97-110
DOI
StatusUdgivet - 2020
NavnLecture Notes in Computer Science
Vol/bind12440
ISSN0302-9743

Emneord

  • Locality-sensitive hashing
  • Nearest neighbor search
  • High-dimensional data
  • Confirmation sampling
  • Query algorithm

Fingeraftryk

Dyk ned i forskningsemnerne om 'Confirmation Sampling for Exact Nearest Neighbor Search'. Sammen danner de et unikt fingeraftryk.

Citationsformater