2017

Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph

Fu, Cong, Xiang, Chao, Wang, Changxu et al.

Understand

Approximate nearest neighbor search (ANNS) is a fundamental problem in databases and data mining.

A scalable ANNS algorithm should be both memory-efficient and fast.
Some early graph-based approaches have shown attractive theoretical guarantees on search time complexity, but they all suffer from the problem of high indexing time complexity.
Recently, some graph-based methods have been proposed to reduce indexing complexity by approximating the traditional graphs; these methods have achieved revolutionary performance on million-scale datasets.

Built on

Multidimensional binary search trees used for associative searching
J. L. Bentley · 1975
Earlier work this paper cites.
A branch and bound algorithm for computing k-nearest neighbors
K. Fukunaga and P. M. Narendra · 1975
Earlier work this paper cites.
The relative neighbourhood graph of a finite planar set
G. T. Toussaint · 1980
Earlier work this paper cites.
On constructing minimum spanning trees in k-dimensional spaces and related problems
A. C.-C. Yao · 1982
Earlier work this paper cites.
Monotonic search networks for computer vision databases
D. Dearholt, N. Gonzales, and G. Kurup · 1988
Earlier work this paper cites.
The r*-tree: an efficient and robust access method for points and rectangles
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger · 1990
Earlier work this paper cites.
Voronoi diagrams—a survey of a fundamental geometric data structure
F. Aurenhammer · 1991
Earlier work this paper cites.
Relative neighborhood graphs and their relatives
J. W. Jaromczyk and G. T. Toussaint · 1992
Earlier work this paper cites.
Database organized on the basis of similarities with applications in computer vision
G. D. Kurup · 1992
Earlier work this paper cites.
Approximate nearest neighbor queries in fixed dimensions
S. Arya and D. M. Mount · 1993
Earlier work this paper cites.
A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces
R. Weber, H.-J. Schek, and S. Blott · 1998
Earlier work this paper cites.
Similarity search in high dimensions via hashing
A. Gionis, P. Indyk, and R. Motwani · 1999
Earlier work this paper cites.
Navigation in a small world
J. M. Kleinberg · 2000
Earlier work this paper cites.
Efficient k-nn search on vertically decomposed data
A. P. de Vries, N. Mamoulis, N. Nes, and M. Kersten · 2002
Earlier work this paper cites.
Robust and fast similarity search for moving object trajectories
L. Chen, M. T. Özsu, and V. Oria · 2005
Earlier work this paper cites.

Similar

Estimating local intrinsic dimension with k-nearest neighbor graphs
J. A. Costa, A. Girotra, and A. Hero · 2005
Cited alongside, same era.
iDistance: An adaptive B+-tree based indexing method for nearest neighbor search
H. V. Jagadish, B. C. Ooi, K.-L. Tan, C. Yu, and R. Zhang · 2005
Cited alongside, same era.
Introduction to information retrieval
C. D. Manning, P. Raghavan, H. Schütze, et al · 2008
Cited alongside, same era.
Optimised kd-trees for fast image descriptor matching
C. Silpa-Anan and R. Hartley · 2008
Cited alongside, same era.
Navigability of complex networks
M. Boguna, D. Krioukov, and K. C. Claffy · 2009
Cited alongside, same era.
Spectral hashing
Y. Weiss, A. Torralba, and R. Fergus · 2009
Cited alongside, same era.
Efficient k-nearest neighbor graph construction for generic similarity measures
W. Dong, C. Moses, and K. Li · 2011
Cited alongside, same era.
Fast approximate nearest-neighbor search with k-nearest neighbor graph
K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang · 2011
Cited alongside, same era.
Product quantization for nearest neighbor search
H. Jegou, M. Douze, and C. Schmid · 2011
Cited alongside, same era.
Approximate nearest neighbor: towards removing the curse of dimensionality
S. Har-Peled, P. Indyk, and R. Motwani · 2012
Cited alongside, same era.
Optimized product quantization for approximate nearest neighbor search
T. Ge, K. He, Q. Ke, and J. Sun · 2013
Cited alongside, same era.
Dsh: data sensitive hashing for high-dimensional k-nnsearch
J. Gao, H. V. Jagadish, W. Lu, and B. C. Ooi · 2014
Cited alongside, same era.

Then

Approximate nearest neighbor algorithm based on navigable small world graphs
Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov · 2014
Later among the works it cites.
Approximate similarity search for online multimedia services on distributed cpu–gpu platforms
G. Teodoro, E. Valle, N. Mariano, R. Torres, W. Meira, and J. H. Saltz · 2014
Later among the works it cites.
Fast and unified local search for random walk based k-nearest-neighbor query in large graphs
Y. Wu, R. Jin, and X. Zhang · 2014
Later among the works it cites.
Cache locality is not enough: high-performance nearest neighbor search with product quantization fast scan
F. André, A.-M. Kermarrec, and N. Le Scouarnec · 2015
Later among the works it cites.
Query-aware locality-sensitive hashing for approximate nearest neighbor search
Q. Huang, J. Feng, Y. Zhang, Q. Fang, and W. Ng · 2015
Later among the works it cites.
Efficient indexing of billion-scale datasets of deep descriptors
A. Babenko and V. Lempitsky · 2016
Later among the works it cites.
FANNG: Fast approximate nearest neighbour graphs
H. Ben and D. Tom · 2016
Later among the works it cites.
Efanna : An extremely fast approximate nearest neighbor search algorithm based on knn graph
Original
C. Fu and D. Cai · 2016
Later among the works it cites.
Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement (v1. 0)
Original
W. Li, Y. Zhang, Y. Sun, W. Wang, W. Zhang, and X. Lin · 2016
Later among the works it cites.
Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs
Original
Y. A. Malkov and D. A. Yashunin · 2016
Later among the works it cites.
Lazylsh: Approximate nearest neighbor search for multiple distance functions with a single index
Y. Zheng, Q. Guo, A. K. Tung, and S. Wu · 2016
Later among the works it cites.
Billion-scale similarity search with gpus
Original
J. Johnson, M. Douze, and H. Jégou · 2017
Closest in time.
Hd-index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces
A. Arora, S. Sinha, P. Kumar, and A. Bhattacharya · 2018
Closest in time.
Fast approximate nearest neighbor search with the navigating spreading-out graph
Original
C. Fu, C. Xiang, C. Wang, and D. Cai · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…