Name
Abstract | ||
|---|---|---|
The k-NN graph has played a central role in increasingly 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 hierarchically and randomly divide the data points into subsets and build an exact neighborhood graph over each subset, achieving a base approximate neighborhood graph; we then repeat this process for several times to generate multiple neighborhood graphs, which are combined to yield a more accurate approximate neighborhood graph. Furthermore, 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. |
Year | Venue | Keywords |
|---|---|---|
2012 | CVPR | empirical accuracy,neighborhood propagation scheme,exact neighborhood graph,base approximate neighborhood graph,accurate approximate neighborhood graph,scalable k-NN graph construction,multiple neighborhood graph,data point,approximate k-NN graph,k-NN graph,visual descriptors,graph construction |
DocType | Citations | PageRank |
Conference | 7 | 0.59 |
References | Authors | |
0 | 1 | |