Nearest neighbor search for arbitrary kernels with explicit embeddings
Résumé
Many algorithms have been proposed to handle efficient search in large databases for simple metrics such as the Euclidean distance. However, few approaches apply to more sophisticated Positive Semi-Definite (PSD) kernels. In this document, we propose for such kernels to use the concept of explicit embedding and to cast the search problem into a Euclidean space. We first describe an exact nearest neighbor search technique which relies on bounds on the approximation of the kernel. We show that, in the case of SIFT descriptors, one can retrieve the nearest neighbor with probability 1 by computing only a fraction of the costly kernels between the query and the database vectors. We then propose to combine explicit embedding with a recent Euclidean approximate nearest neighbor search method and show that it leads to significant improvements with respect to the state-of-the-art methods which rely on an implicit embedding. The database vectors being indexed by short codes, the approach is shown to scale to a dataset comprising 200 million vectors on a commodity server.
De nombreuses méthodes ont été proposées pour la recherche efficace de plus proche voisin au sens de la distance euclidienne dans de grandes bases de données. Cependant, peu d'approches s'intéressent au cas plus général où la distance considérée dérive d'un noyau positif. Dans ce document, nous proposons d'exploiter le concept d'embedding explicite permettant de plonger les données dans un espace Euclidien et d'effectuer la recherche dans cet espace. Nous décrivons tout d'abord une méthode de recherche exacte de plus proche voisin s'appuyant sur une borne de précision de l'approximation du noyau entre la requête et les éléments de la base. Appliquée à des descripteurs SIFT, cette méthode permet de retrouver le plus proche voisin d'une requête avec probabilité 1 tout en ne calculant qu'une fraction des valeurs du noyau entre la requête et les éléments de la base. Nous proposons ensuite de combiner un embedding explicite avec une méthode approchée de recherche de plus proche voisin pour la distance euclidienne, ce qui apporte amélioration substantielle par rapport à des techniques de l'état de l'art s'appuyant sur une approximation implicite. La mise à l'échelle de la méthode est illustrée sur une base de données de 200 millions de vecteurs.
Domaines
Recherche d'information [cs.IR]
Origine : Fichiers produits par l'(les) auteur(s)