Tampere University of Technology

TUTCRIS Research Portal

K-Subspaces Quantization Subspaces for Approximate Nearest Neighbor Search

Research output: Contribution to journalArticleScientificpeer-review


Original languageEnglish
Pages (from-to)1722-1733
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
Publication statusPublished - 2016
Publication typeA1 Journal article-refereed


Approximate Nearest Neighbor (ANN) search has become a popular approach for performing fast and efficient retrieval on very large-scale datasets in recent years, as the size and dimension of data grow continuously. In this paper, we propose a novel vector quantization method for ANN search which enables faster and more accurate retrieval on publicly available datasets. We define vector quantization as a multiple affine subspace learning problem and explore the quantization centroids on multiple affine subspaces. We propose an iterative approach to minimize the quantization error in order to create a novel quantization scheme, which outperforms the state-of-the-art algorithms. The computational cost of our method is also comparable to that of the competing methods.


  • Approximate Nearest Neighbor Search, Vector Quantization, Large-scale learning, Big data

Publication forum classification

Field of science, Statistics Finland