Skip to Main content Skip to Navigation

Approximate Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing

David Arthur 1 Steve Oudot 2, *
* Corresponding author
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We investigate the problem of finding approximate reverse nearest neighbors efficiently in high dimensions. Given a point cloud $P$ and a parameter $\e$, our goal is to preprocess $P$ in a way that enables us to quickly return the set of reverse nearest neighbors of any query point $q$ among the points of $P$, plus possibly a small set of false positives that are $\e$-close to being true reverse nearest neighbors. Although provable solutions exist for this problem in low or fixed dimensions, to this date the methods proposed in high dimensions are mostly heuristic. We propose a method that is both provably-good and provably-efficient in all dimensions, based on a reduction of the problem to a small number of instances of the now classical $\e$-nearest neighbor search and $r$-neighbors reporting problems. Although the former has been extensively studied and elegantly solved in high dimensions using Locality-Sensitive Hashing techniques (LSH), the latter has a complexity that is still not well understood. We propose a new analysis of the LSH scheme for $r$-neighbors reporting, which brings out a meaningful output-sensitive term in the complexity of the problem, and which down the road enables us to solve the approximate reverse nearest problem, thanks to our reduction. Along the way, we propose a method to perform exact nearest neighbor search, whose analysis sheds new light on the problem by introducing a notion of {\em condition number} measuring the inherent complexity of a given instance.
Document type :
Complete list of metadata
Contributor : Steve Oudot Connect in order to contact the contributor
Submitted on : Sunday, October 31, 2010 - 9:20:46 AM
Last modification on : Friday, February 26, 2021 - 9:30:02 AM
Long-term archiving on: : Friday, December 2, 2016 - 4:04:47 AM


Files produced by the author(s)


  • HAL Id : inria-00429459, version 3



David Arthur, Steve Oudot. Approximate Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing. [Research Report] RR-7084, 2009. ⟨inria-00429459v3⟩



Les métriques sont temporairement indisponibles