Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces

By Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, Vladimir V. Krylov. 2012

55 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Ocean Engineering, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

1. Alexander Ponomarenko
2. Yury Malkov
3. Dmitry A. Yashunin
4. Eric Sadit Tellez
5. Vladimir V. Krylov
6. Andrey Logvinov
7. Edgar Chávez
8. Gonzalo Navarro

In Ocean Engineering

1. Yury Malkov
2. Dmitry A. Yashunin
3. Alexander Ponomarenko
4. Gonzalo Navarro
5. Edgar Chávez

In Information Retrieval & Search

1. Alexander Ponomarenko
2. Yury Malkov
3. Leonid Boytsov
4. Bilegsaikhan Naidan
5. Eric Sadit Tellez
6. Edgar Chávez
7. Dmitry A. Yashunin
8. Mario Graff

In Signal Processing

1. Alexander Ponomarenko
2. Yury Malkov
3. Leonid Boytsov
4. Bilegsaikhan Naidan
5. Dmitry A. Yashunin
6. Eric Sadit Tellez
7. Edgar Chávez
8. Mario Graff

Citations in the corpus

• Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “Links to the closest neighbors in a k-NN graph serve as a simple approximation of the Delaunay graph [25, 26] (a graph which guranties that the result of a basic greedy graph traversal is always the nearest neighbor).”
• Singleton indexes for nearest neighbor search (2016, unknown): “Examples of approximate techniques are [27, 7, 13, 1, 16, 15].”
• Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search (2014, methodology): “Experiments with the sparse-vector Wikipedia data set demonstrate that the small world method has a near logarithmic dependence for the number of distance computation on the number of data points, which confirms previous findings [8].”
• Finding Near Neighbors Through Local Search (2015, background): “Malkov et al [4] introduced the Approximate Proximity Graph (APG), an index with excellent searching times.”
• Large Scale Nearest Neighbors Search Based on Neighborhood Graph (2013, background): “Recently several studies on the distributed approach have been proposed [17, 18, 19].”
• Query-Based Improvement Procedure and Self-Adaptive Graph Construction Algorithm for Approximate Nearest Neighbor Search (2015, background): “Several works based on this approach have been proposed [2,4,5].”
• Near neighbor searching with K nearest references (2015, background): “The generalization of Voronoi diagrams to general metric spaces is called a Dirichlet partition, and there are exact and approximate metric indexes based on it [13,17,38,34,35].”
• Approximate nearest neighbor algorithm based on navigable small world graphs (2014, methodology): “The parameter w affects how accurate is determination (recall) of nearest neighbors in the construction algorithm [36].”