Improving the quality of K-NN graphs through vector sparsification: application to image databases

Michael E. Houle, Xiguo Ma, Vincent Oria, Jichao Sun

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


K-nearest neighbor (K-NN) graphs are an essential component of many established methods for content-based image retrieval and automated image annotation. The performance of such methods relies heavily on the semantic quality of the graphs, which can be measured as the proportion of neighbors sharing the same class label as their query images. Due to the noise in image features, the K-NN graphs produced by existing methods may suffer from low semantic quality. In this article, we propose NNF-Descent for the efficient construction of K-NN graphs based on nearest-neighbor and feature descent, in which selective sparsification of feature vectors is interleaved with neighborhood refinement operations in an effort to improve the semantic quality of the result. A variant of the Laplacian Score is proposed for the identification of noisy features local to individual images, whose values are then set to 0 (the global mean value after standardization). We show through extensive experiments on several datasets that NNF-Descent is able to increase the proportion of semantically-related images over unrelated images within the neighbor sets, and that the proposed method generalizes well for other types of data which are represented by high-dimensional feature vectors.

Original languageEnglish (US)
Pages (from-to)259-274
Number of pages16
JournalInternational Journal of Multimedia Information Retrieval
Issue number4
StatePublished - Nov 1 2014

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Media Technology
  • Library and Information Sciences


  • Feature selection
  • Image database
  • Iterative method
  • K-nearest neighbor graph
  • Locally noisy feature
  • Semantic quality
  • Vector sparsification


Dive into the research topics of 'Improving the quality of K-NN graphs through vector sparsification: application to image databases'. Together they form a unique fingerprint.

Cite this