Fast approximate nearest neighbor search with the navigating spreading-out graph

摘要

Approximate nearest neighbor search (ANNS) is a fundamental problem inmachine learning and computer vision. An ANNS algorithm is required to beefficient on both memory use and search performance. Recently, graph basedmethods have achieved revolutionary performance on public datasets. Theearliest approach GNNS is a greedy algorithm and based on a$k$-nearest-neighbor graph ($k$NN graph). The improvements of GNNS mainly focuson two aspects: (1) Some provide better initial search position to prevent thesearch from being stuck in local optima. (2) Others try to construct bettergraphs for faster traversing and neighbor locating. However, we find thereexists three problems with these works, the unconnected cluster problem, thedetouring problem and the large index problem (memory-inefficient for largescale search). In this paper, we present a novel graph structure namedNavigating Spreading-out Graph (NSG) to tackle above three problemssimultaneously, without introducing any other index structures. Extensiveexperiments show that our algorithm outperforms all the existing algorithmssignificantly. What's more, our algorithm outperforms the existing approach ofTaobao (Alibaba Group), and has been integrated into their search engine forbillion scale search.