Nearest Neighbors Using Compact Sparse Codes

Anoop Cherian 1
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : In this paper, we propose a novel scheme for approximate nearest neighbor (ANN) retrieval based on dictionary learning and sparse coding. Our key innovation is to build compact codes, dubbed SpANN codes, using the active set of sparse coded data. These codes are then used to index an inverted file table for fast retrieval. The active sets are often found to be sensitive to small differences among data points, resulting in only near duplicate retrieval. We show that this sensitivity is related to the coherence of the dictionary; small coherence resulting in better retrieval. To this end, we propose a novel dictionary learning formulation with incoherence constraints and an efficient method to solve it. Experiments are conducted on two state-of-the-art computer vision datasets with 1M data points and show an order of magnitude improvement in retrieval accuracy without sacrificing memory and query time compared to the state-of-the-art methods.
Type de document :
Communication dans un congrès
ICML - 31st International Conference on Machine Learning, Jun 2014, Beijing, China. 2014
Liste complète des métadonnées


https://hal.inria.fr/hal-01057690
Contributeur : Thoth Team <>
Soumis le : mercredi 3 décembre 2014 - 16:59:12
Dernière modification le : vendredi 23 septembre 2016 - 01:04:10
Document(s) archivé(s) le : lundi 9 mars 2015 - 05:51:26

Fichier

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

Identifiants

  • HAL Id : hal-01057690, version 1

Collections

Citation

Anoop Cherian. Nearest Neighbors Using Compact Sparse Codes. ICML - 31st International Conference on Machine Learning, Jun 2014, Beijing, China. 2014. <hal-01057690>

Partager

Métriques

Consultations de
la notice

270

Téléchargements du document

762