Highly Efficient Disk-based Nearest Neighbor Search on Extended Neighborhood Graph

Nearest neighbor search (NN search) plays a fundamental role in many disciplines. According to recent studies, graph-based search methods show superior performance over other types of methods. In order to accommodate the high dimensionality as well as the growing data-scale, the disk-based NN search in which the index graph and the full-precision vectors are kept in SSD has become a promising direction. This paper optimizes the disk-based NN search from three perspectives. Firstly, an eXtended Neighborhood Graph (XN-Graph) structure is proposed. In contrast to the existing index graphs, the out-edges of the graph neighborhood are collected from much wider coverage of the data space. It therefore reduces the number of hops during NN search, which in turn reduces the search latency. Additionally, a dataset partitioning method called Boundary-adaptive Balanced Partition is proposed to facilitate the graph construction in cases where the system cannot handle large datasets in a single round. Moreover, an efficient hybrid NN search method called In-Memory First Search is proposed. Compared to the existing methods, it considerably reduces the CPU idle times. With the support of XN-Graph, it shows 1.5-3 times lower search latency than SOTA methods. On billion-scale datasets, its QPS is still above 4000 when Recall@10 is as high as 0.9.