Paper Info
Title
Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces
Abstract
We propose a novel approach for solving the approximate nearest neighbor search problem in arbitrary metric spaces. The distinctive feature of our approach is that we can incrementally build a non-hierarchical distributed structure for given metric space data with a logarithmic complexity scaling on the size of the structure and adjustable accuracy probabilistic nearest neighbor queries. The structure is based on a small world graph with vertices corresponding to the stored elements, edges for links between them and the greedy algorithm as base algorithm for searching. Both search and addition algorithms require only local information from the structure. The performed simulation for data in the Euclidian space shows that the structure built using the proposed algorithm has navigable small world properties with logarithmic search complexity at fixed accuracy and has weak (power law) scalability with the dimensionality of the stored data.
Year
DOI
Venue
2012
10.1007/978-3-642-32153-5_10
SISAP
Keywords
Field
DocType
addition algorithm,arbitrary metric space,base algorithm,approximate nearest neighbor search,dimensional general metric space,logarithmic search complexity,adjustable accuracy probabilistic,metric space data,euclidian space,greedy algorithm,proposed algorithm,similarity search,nearest neighbor,metric space
Locality-sensitive hashing,Fixed-radius near neighbors,Best bin first,Ball tree,Computer science,Algorithm,Nearest neighbor graph,Artificial intelligence,Cover tree,Large margin nearest neighbor,Nearest neighbor search,Machine learning
Conference
Citations 
PageRank 
References 
12
0.70
29
Authors
4
Name
Order
Citations
PageRank
Yury Malkov1683.06
Alexander Ponomarenko2623.32
A. Logvinov3582.65
Vladimir Krylov4572.25