Beyond "project and sign" for cosine estimation with binary codes

Raghavendran Balu 1 Teddy Furon 1 Hervé Jégou 1
1 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Many nearest neighbor search algorithms rely on encoding real vectors into binary vectors. The most common strategy projects the vectors onto random directions and takes the sign to produce so-called sketches. This paper discusses the sub-optimality of this choice, and proposes a better encoding strategy based on the quantization and reconstruction points of view. Our second contribution is a novel asymmetric estimator for the cosine similarity. Similar to previous asymmetric schemes, the query is not quantized and the similarity is computed in the compressed domain. Both our contribution leads to improve the quality of nearest neighbor search with binary codes. Its efficiency compares favorably against a recent encoding technique.
Type de document :
Communication dans un congrès
ICASPP - International Conference on Acoustics, Speech, and Signal Processing, May 2014, Florence, Italy. 2014
Liste complète des métadonnées

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


https://hal.inria.fr/hal-00942075
Contributeur : Hervé Jégou <>
Soumis le : mardi 4 février 2014 - 16:13:04
Dernière modification le : mercredi 11 avril 2018 - 01:39:23
Document(s) archivé(s) le : dimanche 9 avril 2017 - 08:47:47

Fichiers

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

Identifiants

  • HAL Id : hal-00942075, version 1

Citation

Raghavendran Balu, Teddy Furon, Hervé Jégou. Beyond "project and sign" for cosine estimation with binary codes. ICASPP - International Conference on Acoustics, Speech, and Signal Processing, May 2014, Florence, Italy. 2014. 〈hal-00942075〉

Partager

Métriques

Consultations de la notice

465

Téléchargements de fichiers

474