Explicit embeddings for nearest neighbor search with Mercer kernels

Anthony Bourrier 1, 2, 3 Florent Perronnin 4 Rémi Gribonval 2 Patrick Pérez 3 Hervé Jégou 5
1 GIPSA-VIBS - VIBS
GIPSA-DIS - Département Images et Signal
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
5 LinkMedia - Creating and exploiting explicit links between multimedia fragments
Inria Rennes – Bretagne Atlantique , IRISA-D6 - MEDIA ET INTERACTIONS
Abstract : Many approximate nearest neighbor search algorithms operate under memory constraints, by computing short signatures for database vectors while roughly keeping the neighborhoods for the distance of interest. Encoding procedures designed for the Euclidean distance have attracted much attention in the last decade. In the case where the distance of interest is based on a Mercer kernel, we propose a simple, yet effective two-step encoding scheme: first, compute an explicit embedding to map the initial space into a Euclidean space; second, apply an encoding step designed to work with the Euclidean distance. Comparing this simple baseline with existing methods relying on implicit encoding, we demonstrate better search recall for similar code sizes with the chi-square kernel in databases comprised of visual descriptors, outperforming concurrent state-of-the-art techniques by a large margin.
Type de document :
Article dans une revue
Journal of Mathematical Imaging and Vision, Springer Verlag, 2015, pp.1-10. <10.1007/s10851-015-0555-2>
Liste complète des métadonnées


https://hal.inria.fr/hal-00722635
Contributeur : Anthony Bourrier <>
Soumis le : mardi 17 février 2015 - 17:00:10
Dernière modification le : mercredi 2 août 2017 - 10:11:35
Document(s) archivé(s) le : lundi 18 mai 2015 - 10:45:55

Fichier

ee_ann_single.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Anthony Bourrier, Florent Perronnin, Rémi Gribonval, Patrick Pérez, Hervé Jégou. Explicit embeddings for nearest neighbor search with Mercer kernels. Journal of Mathematical Imaging and Vision, Springer Verlag, 2015, pp.1-10. <10.1007/s10851-015-0555-2>. <hal-00722635v4>

Partager

Métriques

Consultations de
la notice

1208

Téléchargements du document

762