Permutation Search Methods are Efficient, Yet Faster Search is Possible

By Bilegsaikhan Naidan, Leonid Boytsov, Eric Nyberg. 2015

59 citations recorded by the source corpus.

We survey permutation-based methods for approximate k-nearest neighbor search. In these methods, every data point is represented by a ranked list of pivots sorted by the distance to this point. Such ranked lists are called permutations. The underpinning assumption is that, for both metric and non-metric spaces, the distance between permutations is a good proxy for the distance between original points. Thus, it should be possible to efficiently retrieve most true nearest neighbors by examining only a tiny subset of data points whose permutations are similar to the permutation of a query. We further test this assumption by carrying out an extensive experimental evaluation where permutation methods are pitted against state-of-the art benchmarks (the multi-probe LSH, the VP-tree, and proximity-graph based retrieval) on a variety of realistically large data set from the image and textual domain. The focus is on the high-accuracy retrieval methods for generic spaces. Additionally, we assume that both data and indices are stored in main memory. We find permutation methods to be reasonably efficient and describe a setup where these methods are most useful. To ease reproducibility, we make our software and data sets publicly available.

Subfields: Computer Vision and Pattern Recognition, Ocean Engineering, Optimization & Training, 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 Vision and Pattern Recognition

In Ocean Engineering

In Optimization & Training

In Signal Processing

Citations in the corpus

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “For that purpose, we used a built-in nmslib testing system which had scripts to run tests from [34].”
FANNG: Fast Approximate Nearest Neighbour Graphs (2016, methodology): “The simplest way to use directed graphs for finding the nearest neighbour to an arbitrary query point is to start at some vertex in the graph, test each outgoing edge from that vertex and follow the first edge that gets closer to the query point.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, unknown): “In [34], a simple polynomial pruner is employed.”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, background): “However, according to the evaluation of [77], NSW provides limited best tradeoffs between efficiency and effectiveness compared to non-graph-based indexes, because its search complexity is polylogarithmic [73].”