Fast Approximate Nearest Neighbor Search via k-Diverse Nearest Neighbor Graph

Authors

  • Yan Xiao University of Chinese Academy of Sciences;  Institute of Computing Technology, Chinese Academy of Sciences
  • Jiafeng Guo University of Chinese Academy of Sciences;  Institute of Computing Technology, Chinese Academy of Sciences
  • Yanyan Lan University of Chinese Academy of Sciences; Institute of Computing Technology, Chinese Academy of Sciences
  • Jun Xu University of Chinese Academy of Sciences; Institute of Computing Technology, Chinese Academy of Sciences
  • Xueqi Cheng University of Chinese Academy of Sciences; Institute of Computing Technology, Chinese Academy of Sciences

Keywords:

indexing, nearest neighbor search

Abstract

Approximate nearest neighbor search is a fundamental problem and has been studied for a few decades. Recently graph-based indexing methods have demonstrated their great efficiency, whose main idea is to construct neighborhood graph offline and perform a greedy search starting from some sampled points of the graph online. Most existing graph-based methods focus on either the precise k-nearest neighbor (k-NN) graph which has good exploitation ability, or the diverse graph which has good exploration ability. In this paper, we propose the k-diverse nearest neighbor (k-DNN) graph, which balances the precision and diversity of the graph, leading to good exploitation and exploration abilities simultaneously. We introduce an efficient indexing algorithm for the construction of the k-DNN graph inspired by a well-known diverse ranking algorithm in information retrieval (IR). Experimental results show that our method can outperform both state-of-the-art precise graph and diverse graph methods.

Downloads

Published

2018-04-29

How to Cite

Xiao, Y., Guo, J., Lan, Y., Xu, J., & Cheng, X. (2018). Fast Approximate Nearest Neighbor Search via k-Diverse Nearest Neighbor Graph. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12138