Publications
CONFERENCE (INTERNATIONAL) Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search
9th International Conference on Similarity Search and Applications (SISAP 2016)
October 24, 2016
In this paper, we address the problems with fast proximity searches for high-dimensional data by using a graph as an index. Graphbased methods that use the k-nearest neighbor graph (KNNG) as an index perform better than tree-based and hash-based methods in terms of search precision and query time. To further improve the performance of the KNNG, the number of edges should be increased. However, increasing the number takes up more memory, while the rate of performance improvement gradually falls off. Here, we propose a pruned bi-directed KNNG (PBKNNG) in order to improve performance without increasing the number of edges. Different directed edges for existing edges between a pair of nodes are added to the KNNG, and excess edges are selectively pruned from each node. We show that the PBKNNG outperforms the KNNG for SIFT and GIST image descriptors. However, the drawback of the KNNG is that its construction cost is fatally expensive. As an alternative, we show that a graph can be derived from an approximate neighborhood graph, which costs much less to construct than a KNNG, in the same way as the PBKNNG and that it also outperforms a KNNG.
Paper :
Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search
(external link)