Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. (December 2019)

• Record Type: Journal Article
• Authors: Vargas Muñoz, Javier; Gonçalves, Marcos A.; Dias, Zanoni; da S. Torres, Ricardo
• Is Part Of: Pattern recognition. Volume 96(2019:Dec.)
• Publication Date: 2019-12
• Subjects: Approximate nearest neighbors search -- Graph-based search -- Hierarchical clustering -- Guided search; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.106970
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Nearest Neighbors (NN) search based on NN-graphs outperforms classical approaches. Clustering results are used for creating efficient NN-graphs. Guided navigation on NN-graphs improves significantly the effectiveness results. Non-randomized initial vertex selection improves search results at high speedups. Abstract: This paper presents a novel approach to perform fast approximate nearest neighbors search in high dimensional data, using a nearest neighbor graph created over large collections. This graph is created based on the fusion of multiple hierarchical clustering results, where a minimum-spanning-tree structure is used to connect all elements in a cluster. We propose a novel search technique to guide the navigation on the graph without computing exhaustively the distances to all neighbors in each step of the search, just to those in the direction of the query. The objective is to determine the nearest point to the query with a few number of distance calculations. We experimented in three datasets of 1 million SIFT, GIST, and GloVe features. Results show better speedups than another graph-based technique, and competitive speedups at high recall values when compared to classic and recent state-of-the-art techniques.