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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/hal-01057690
Contributor : Thoth Team <>
Submitted on : Wednesday, December 3, 2014 - 4:59:12 PM
Last modification on : Sunday, March 10, 2019 - 11:10:45 AM
Long-term archiving on : Monday, March 9, 2015 - 5:51:26 AM

File

spannicml2014.pdf
Files produced by the author(s)

Identifiers

  • 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. pp.1053-1061. ⟨hal-01057690⟩

Share

Metrics

Record views

437

Files downloads

1157