High-Dimensional Indexing by Sparse Approximation

Pedro Borges, André Mourão, João Magalhães

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)


In this paper we propose a high-dimensional indexing technique, based on sparse approximation techniques to speed up the search and retrieval of similar images given a query image feature vector. Feature vectors are stored on an inverted indexed based on a sparsifying dictionary for 10 regression, optimized to reduce the data dimensionality. It concentrates the energy of the original vector on a few coefficients of a higher dimensional representation. The index explores the coefficient locality of the sparse representations, to guide the search through the inverted index. Evaluation on three large-scale datasets showed that our method compares favorably to the state-of-the-art. On a 1 million dataset of SIFT vectors, our method achieved 60.8% precision at 50 by inspecting only 5% of the full dataset, and by using only 1/4 of the time a linear search takes.
Original languageEnglish
Title of host publicationProceedings of the 5th ACM on International Conference on Multimedia Retrieval, Shanghai, China, June 23-26, 2015
PublisherACM Press
Number of pages8
ISBN (Print) 978-145033274-3
Publication statusPublished - 2015


  • Computer Science
  • Artificial Intelligence
  • Imaging Science & Photographic Technology
  • High-dimensional indexing
  • image indexing
  • Approximate nearest neighbor search
  • Sparse coding
  • l 0 penalty


Dive into the research topics of 'High-Dimensional Indexing by Sparse Approximation'. Together they form a unique fingerprint.

Cite this