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

David Arthur 1 Steve Oudot 2, *
* Auteur correspondant
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : Nous étudions le problème de la recherche efficace de plus proches voisins inverses en grandes dimensions. Étant donné un nuage de points $P$ et un paramètre $\e$, notre objectif est de pré-traiter le nuage $P$ de telle sorte à pouvoir trouver rapidement l'ensemble des plus proches voisins inverses d'un point de requête $q$ quelconque, plus éventuellement un petit nombre de faux positifs qui sont proches d'être des plus proches voisins inverses de $q$. Alors que des solutions efficaces et prouvées existent pour ce problème en dimensions petites ou fixées, à ce jour les méthodes proposées en grandes dimensions sont essentiellement heuristiques. Nous proposons une méthode à la fois efficace et prouvée en toutes dimensions, basée sur une réduction du problème à un petit nombre d'instances des problèmes classiques de recherche de plus proche voisin approché et de recherche exhaustive de voisins à distance $r$ fixée. La complexité intrinsèque de ce dernier problème reste peu connue. Nous proposons une nouvelle analyse du comportement de certaines techniques de hachage sensibles à la localisation (LSH) sur ce problème, qui met en évidence une borne dépendant de la taille de la sortie, et qui, combinée à un relèvement non-isométrique des points en dimension plus grande, permet de résoudre le problème de la recherche de plus proches voisins inverses efficacement, via la réduction citée précédemment. Dans la foulée nous proposons également une méthode pour effectuer des recherches de plus proches voisins exacts, dont la complexité est paramétrée par un indice de {\em conditionnement} mesurant la difficulté intrinsèque d'une instance particulière du problème.
Type de document :
Rapport
[Research Report] RR-7084, INRIA. 2010
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00429459
Contributeur : Steve Oudot <>
Soumis le : lundi 22 novembre 2010 - 20:22:39
Dernière modification le : samedi 27 janvier 2018 - 01:32:01
Document(s) archivé(s) le : samedi 3 décembre 2016 - 02:56:41

Fichier

RR-7084.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00429459, version 5

Collections

Citation

David Arthur, Steve Oudot. Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing. [Research Report] RR-7084, INRIA. 2010. 〈inria-00429459v5〉

Partager

Métriques

Consultations de la notice

541

Téléchargements de fichiers

323