Learning to Route in Similarity Graphs

The current approaches for efficient NNS mostly belong to three separate lines of research. The first family of methods, Recently similarity graphs became the leading based on partition trees (Bentley, 1975; Sproull, 1991; paradigm for efficient nearest neighbor search, McCartin-Lim et al., 2012; Dasgupta & Freund, 2008; Dasgupta outperforming traditional tree-based and LSHbased & Sinha, 2013), hierarchically split the search space methods. Similarity graphs perform the into a large number of regions, corresponding to tree leaves, search via greedy routing: a query traverses the and query visits only a limited number of promising regions graph and in each vertex moves to the adjacent when searching. The second, locality-sensitive hashing vertex that is the closest to this query. In practice, methods (Indyk & Motwani, 1998; Datar et al., 2004; Andoni similarity graphs are often susceptible to local & Indyk, 2008; Andoni et al., 2015) map the database minima, when queries do not reach its nearest points into a number of buckets using several hash functions neighbors, getting stuck in suboptimal vertices. In such that the probability of collision is much higher this paper we propose to learn the routing function for nearby points than for points that are further apart. At that overcomes local minima via incorporating information the search stage, a query is also hashed, and distances to about the graph global structure. In particular, all the points from the corresponding buckets are evaluated.