Scalable k-NN graph construction
for visual descriptors

Jing Wang1, Jingdong Wang2, Gang Zeng1, Zhuowen Tu2,3, Rui Gan1 and Shipeng Li2
1Peking University  2Microsoft Research Asia
3Lab of Neuro Imaging and Department of Computer Science, UCLA


The k-NN graph has played a central role in increas- ingly popular data-driven techniques for various learning and vision tasks; yet, finding an efficient and effective way to construct k-NN graphs remains a challenge, especially for large-scale high-dimensional data. In this paper, we propose a new approach to construct approximate k-NN graphs with emphasis in: efficiency and accuracy. We hi- erarchically and randomly divide the data points into sub- sets and build an exact neighborhood graph over each sub- set, achieving a base approximate neighborhood graph; we then repeat this process for several times to generate mul- tiple neighborhood graphs, which are combined to yield a more accurate approximate neighborhood graph. Further- more, we propose a neighborhood propagation scheme to further enhance the accuracy. We show both theoretical and empirical accuracy and efficiency of our approach to k-NN graph construction and demonstrate significant speed-up in dealing with large scale visual data.



| PDF |


  author    = "Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, Shipeng Li",
  title     = "Scalable k-NN graph construction for visual descriptors",
  booktitle = "CVPR",
  year      = "2012",


Performance Comparison
Accuracy vs. Time performance comparisons over Caltech 101, Recognition Benchmark, Imagenet, and TinyImage
Performance for object discovery
Performance for object discovery over Oxford5K dataset
Visual results
Visual Example 1
Image ranking result comparison between rank-order distance and Euclidean distance. The first image in each row are the query and the images with green dot at bottom right are the correct images containing the same face as the query. (a) gives the results of using Euclidean distance and (b) gives the results of using Rank-order distance.
Visual Example 2
CObject discovery results: each row represents one discovered object cluster and the images are randomly picked out from the cluster.
©Copyright Jingdong Wang 2012
HTML Hit Counters