Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions

Abstract

The long-standing problem of efficient nearest-neighbor (NN) search has ubiqui-tous applications ranging from astrophysics to MP3 fingerprinting to bioinformat-ics to movie recommendations. As the dimensionality of the dataset increases, ex-act NN search becomes computationally prohibitive; (1+휖) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the first time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments on high-dimensional datasets show that our algorithm often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior. 1