Explicit embeddings for nearest neighbor search with Mercer kernels - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Journal of Mathematical Imaging and Vision Year : 2015

Explicit embeddings for nearest neighbor search with Mercer kernels

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.
Fichier principal
Vignette du fichier
ee_ann_single.pdf (1.75 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00722635 , version 1 (02-08-2012)
hal-00722635 , version 2 (06-01-2015)
hal-00722635 , version 3 (28-01-2015)
hal-00722635 , version 4 (17-02-2015)

Identifiers

Cite

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, 2015, 52 (3), pp.459-468. ⟨10.1007/s10851-015-0555-2⟩. ⟨hal-00722635v4⟩
836 View
1312 Download

Altmetric

Share

Gmail Facebook X LinkedIn More