PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Cong Fu, Chao Xiang, Changxu Wang, Deng Cai

arXiv:1707.00143v10cs.LG

TL;DR

Graph-based ANNS methods need fast, memory-efficient search at billion-node scale, but prior approaches have theoretical, indexing, or scalability limitations. The paper analyzes monotonic search networks, proposes MRNG and its practical NSG approximation, and reports superior search performance, low memory usage, and billion-node deployment in Taobao’s search engine.

  • Problem

    Prior graph-based ANNS methods either lack rigorous theoretical support or retain indexing and scalability limitations that hinder billion-node applications.

  • Method

    The paper analyzes MSNETs, designs MRNG for close-logarithmic search complexity, and approximates it with NSG using four graph-design objectives simultaneously.

  • Results

    NSG outperforms state-of-the-art methods in search performance, uses the smallest memory among graph-based methods, and is integrated into Taobao’s billion-node search engine.

  • Takeaways & Limitations

    NSG provides a graph index reported as practical for massive ANNS problems and deployed at billion-node scale in an e-commerce search engine.

  • Takeaways & Limitations

    Some MSNETs can have out-degrees that grow with the dataset size, and NSG may still suffer degree explosion at navigating or dense-area nodes.

Abstract

from arXiv · show

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. Yet, they still can not scale to billion-node databases. In this paper, to further improve the search-efficiency and scalability of graph-based methods, we start by introducing four aspects: (1) ensuring the connectivity of the graph; (2) lowering the average out-degree of the graph for fast traversal; (3) shortening the search path; and (4) reducing the index size. Then, we propose a novel graph structure called Monotonic Relative Neighborhood Graph (MRNG) which guarantees very low search complexity (close to logarithmic time). To further lower the indexing complexity and make it practical for billion-node ANNS problems, we propose a novel graph structure named Navigating Spreading-out Graph (NSG) by approximating the MRNG. The NSG takes the four aspects into account simultaneously. Extensive experiments show that NSG outperforms all the existing algorithms significantly. In addition, NSG shows superior performance in the E-commercial search scenario of Taobao (Alibaba Group) and has been integrated into their search engine at billion-node scale.

1 INTRODUCTION

The paper targets graph-based ANNS methods that lack rigorous support and do not yet scale adequately to billion-node applications. It introduces MRNG and its practical approximation, NSG, to combine favorable search complexity, scalability, and memory efficiency.

  • Motivation: Graph-based ANNS approximations generally lack rigorous theoretical support and remain insufficient for billion-node applications.The paper identifies this gap as a motivation for designing a more theoretically grounded and scalable graph index.
  • Motivation: Greedy graph search improves when the search path is shortened and the graph’s out-degree is reduced.The search procedure follows neighbors while selecting points closer to the query, so these graph properties directly shape traversal effort.
  • Contributions: MRNG guarantees an expected average search time complexity close to logarithmic time.It is introduced as a graph structure motivated by the theoretical properties of monotonic search networks.
  • Contributions: NSG approximates MRNG while simultaneously ensuring connectivity, lowering average out-degree, shortening search paths, and reducing index size.The approximation significantly reduces indexing complexity compared with MRNG and is intended for massive problems.
  • Contributions: Extensive experiments report that NSG outperforms state-of-the-art methods in search performance with the smallest memory usage among graph-based methods.The method was also tested in Taobao’s e-commerce search scenario and integrated into its billion-node search engine.

2 PRELIMINARIES

The preliminaries define ANNS, motivate approximate retrieval as a precision–search-time trade-off, and review tree, hashing, quantization, and graph-based approaches. They emphasize that graph methods often search more efficiently, while established graph structures face theoretical, indexing, or degree-related challenges.

  • Problem Setting: ANNS preprocesses a finite point set to return points near a query efficiently, trading a small accuracy loss for shorter search time.The approximate K-nearest-neighbor formulation requires returned points to satisfy a distance bound relative to the true nearest neighbors.
  • Problem Setting: Precision measures the fraction of returned neighbors that belong to the correct nearest-neighbor set, and higher precision corresponds to smaller approximation error.The paper uses precision as its evaluation metric instead of calculating epsilon directly.
  • Non-Graph-Based ANNS Methods: Non-graph-based methods partition or quantize high-dimensional space, but locating neighboring regions can require checking many points, especially as dimension increases.The paper contrasts this behavior with graph indices, which represent neighbor relationships more directly.
  • Graph-Based ANNS Methods: Graph-based ANNS uses nodes and edges representing data points and neighbor relationships, commonly searched with a greedy graph-search algorithm.The reviewed graph families include kNN-based, Delaunay-related, RNG-based, and navigable small-world structures.
  • Graph-Based ANNS Methods: Delaunay-, RNG-, and navigable-small-world-based methods offer useful properties but face high degree, indexing, or insufficient theoretical guarantees.Delaunay graphs can become almost fully connected in high dimensions; RNG preprocessing is expensive, while navigable-small-world complexity is empirically estimated.
  • Graph-Based ANNS Methods: Randomized Neighborhood Graphs prove O((log n)^3) search complexity, but their indexing complexity is too high.A variant called RNG* is proposed in the reviewed work to reduce indexing complexity.

3 ALGORITHMS AND ANALYSIS

The paper analyzes graph-based ANNS through connectivity, out-degree, search-path length, and index size, then develops MRNG and its practical approximation NSG. MRNG offers close-logarithmic expected search complexity, while NSG reduces indexing cost and preserves sparse, connected, efficient search.

  • 3.1 Motivation: Graph search efficiency depends on greedy-hop count and the cost of selecting the next node, motivating simultaneous reduction of path length and average out-degree.The paper also requires graph connectivity and a small index for large-scale ANNS.
  • 3.2 Analysis On Monotonic Search Networks: MSNETs guarantee monotonic paths between every node pair, and Algorithm 1 can find these paths without backtracking.For randomly distributed points, the expected monotonic-path length grows close to O(log n) in high dimensions.
  • 3.2 Analysis On Monotonic Search Networks: RNG’s strict edge selection can create non-monotonic paths, whereas MRNG’s recursive strategy provides at least one monotonic path between any two nodes.MRNG is directed and differs from RNG by allowing an edge even when its lune contains points, subject to its recursive selection rule.
  • 3.3 Monotonic Relative Neighborhood Graph: MRNG has constant maximum degree independent of n, yielding expected search complexity O(cn^(1/d)/Δr), with c independent of n and Δr decreasing slowly.Its construction remains impractical at scale because the indexing complexity is at least O(n^(2−2/(1+d)+ε) + n^2 log n + n^3).
  • 3.5 NSG: A Practical Approximation For MRNG: NSG approximates MRNG using candidate search, bounded degree, and tree spanning to target low indexing cost while retaining sparse, connected graph search.The empirical indexing complexity is lower than MRNG’s O(n^2 log n + cn^2), with candidate edge selection O(nlc) when candidate count and degree limit are small.
  • 3.5 NSG: A Practical Approximation For MRNG: NSG’s empirical search complexity is close to O(log n), and its degree upper bound, connectivity operation, and graph-only index improve all four design criteria.The approximation may sacrifice some worst-case performance, while a high-quality approximate kNN graph and proper degree limit minimize detours.

4 EXPERIMENTS

The experiments compare graph-based and non-graph-based ANNS methods across datasets, evaluating performance, connectivity, degree, search-path proxies, index size, and indexing time. NSG achieves strong search performance while maintaining connectivity and the smallest graph index among the compared methods.

  • Experimental setup: The experiments cover tree-based, hashing-based, quantization-based, and graph-based ANNS methods on four million-scale datasets.SIFT1M, GIST1M, RAND4M, and GAUSS5M are evaluated, with validation-based tuning focused on precision above 90%.
  • Search performance: NSG outperforms the other graph-based methods on all four datasets in the high-precision region.The study uses single-threaded search and compares optimized implementations or implementations reproduced from published methods.
  • Graph connectivity: Only NSG and HNSW guarantee connectivity across the evaluated datasets, while other methods exhibit multiple strongly connected components on some datasets.NSG and HNSW start searches from fixed nodes, requiring reachability from those starting points.
  • Degree and search path: NSG is sparser than competing graph-based methods and has a lower empirical product of average out-degree and search-path length.Because graph-based methods use the same search algorithm and spend most time on distance calculations, this product serves as a rough search-performance indicator.
  • Index size: NSG has the smallest indices across the four datasets, measuring about 1/2–1/3 the index size of HNSW.Its small index results from approximating MRNG and limiting the maximum out-degree.

C. Some Interesting Points:

The additional experiments examine how NSG behaves with intrinsic dimension, precision, dataset scale, indexing strategy, and distributed deployment. NSG remains effective at high precision and supports large-scale search, while its performance and indexing cost depend on data and system configuration.

  • Data characteristics: As local intrinsic dimension increases, the performance gap between NSG and other algorithms widens.The comparison is based on the four-dataset results in Figure 6.
  • High-precision search: At 99% precision, NSG is tens of times faster than serial scan on SIFT1M and GIST1M and remains faster on RAND4M and GAUSS5M.Many other methods become slower than serial scan as required precision increases.
  • Indexing: NSG indexing is nearly the fastest among graph-based methods but remains much slower than non-graph-based methods.The paper reports preprocessing times for graph-based methods in Table 3.
  • Compared graph structures: HNSW and FANNG omit a large proportion of nearest-neighbor edges, while FANNG also uses a non-monotonic RNG basis.The paper links these properties to detour problems and poorer search performance for FANNG; HNSW instead uses multilayer shortcuts at larger index size.
  • Compared graph structures: KGraph and Efanna use much larger out-degrees than NSG, which significantly damages their performance.Their kNN graphs approximate the highly connected Delaunay graph, requiring large k to approximate monotonicity.
  • Complexity scaling: Estimated NSG search complexity is about O(n^(1/d)), with d approximately the intrinsic dimension, and about O(K^0.46) or O((log K)^2.7) in required-neighbor count.The estimates are obtained from fitted scaling curves on SIFT1M and GIST1M.
  • Large-scale evaluation: On 100M DEEP1B vectors, NSG-16core outperforms Faiss-GPU and is about 430 times faster than Serial-16core at 99% precision.Building sixteen subset indices sequentially takes 3.53 hours, while one 6.25M-vector NSG takes 794 seconds.
  • E-commerce deployment: On Taobao’s roughly 2-billion-vector dataset, a 32-partition distributed NSG achieves about 5 ms response time at 98% precision.Indexing takes about 12 hours per partition, while the baseline cannot meet the whole-dataset response-time requirement.

5 DISCUSSIONS

NSG delivers high search performance at high precision, but requires substantially more memory and preprocessing time than popular quantization- and hashing-based methods. Its indexing cost also makes a single build impractical on large datasets, motivating distributed search and future incremental-indexing work.

  • NSG achieves very high search performance at high precision but uses more memory and preprocessing time than IVFPQ and LSH.It is best suited to high-precision, fast-response scenarios when sufficient memory is available.
  • Building one NSG on a large dataset is impractical, so distributed search may be appropriate for deployment.
  • Incremental indexing remains a future-work direction for NSG.

6 CONCLUSIONS

The paper introduces MRNG for approximately logarithmic search complexity and NSG as a practical approximation that jointly targets four graph-design objectives. Experiments report significant gains across multiple aspects, including billion-scale deployment in Taobao’s search engine.

  • MRNG ensures approximately logarithmic search complexity, while NSG approximates it for practical large-scale use.
  • NSG jointly addresses connectivity, average out-degree, search-path length, and index size.
  • NSG significantly outperforms other state-of-the-art algorithms across different aspects in extensive experiments.
  • NSG outperforms Taobao’s baseline and has been integrated into its search engine for billion-scale search.

A PROOF FOR THEOREM 1

The proof establishes that greedy search without back-tracing follows a path whose distances to the query decrease monotonically. This guarantees that the search can reach any target node within at most n−1 iterations.

  • The proof considers any points p and q and studies greedy search from p toward q on the MSNET.
  • At most n−1 iterations suffice to reach q; otherwise, a strictly decreasing sequence over n nodes would contradict q’s absence from the dataset.
  • At each iteration, the current path remains monotonic because the selected neighbor is no farther from q than any improving neighbor.
  • The induction covers the base case and extends monotonicity from t=m to t=m+1 iterations.
  • Therefore, greedy search without back-tracing can find a monotonic path between any two nodes in the MSNET.

B PROOF FOR THEOREM 2

The proof analyzes monotonic-path length in the MSNET and establishes the MRNG’s structural properties, including connectivity-compatible navigation and bounded average out-degree. The accompanying experiment compares distance calculations and graph connectivity across methods.

  • Path-length analysis: A monotonic path is represented by a decreasing sequence of distances from successive nodes to query q, extended with q’s nearest-neighbor distance.
  • Path-length analysis: The proof converts successive distance values into concentric open spheres around q and bounds their number using the minimum distance gap Δr.
  • Path-length analysis: Under uniformly distributed data, density is constant, enabling bounds relating dataset size n, space volume, and the maximal distance R.
  • Path-length analysis: The proof shows the relevant growth functions have the same order and concludes that expected monotonic-path length is O(n
  • MRNG properties: MRNG contains a monotonic path between any two nodes and has average out-degree bounded by a constant depending only on dimension d, not n.
  • Empirical comparison: Figure 8 compares distance calculations for four algorithms, with lower-right positions preferred; NSG uses tens of times fewer calculations than the alternatives.
  • Empirical comparison: Table 4 records strongly connected components, counting NSG and HNSW as one when all points are reachable from their fixed search starts.

G EXPERIMENTS ON THE CONNECTIVITY

The experiments show that NSG and HNSW guarantee graph connectivity, whereas the other evaluated graph methods do not.

  • Only HNSW and NSG guarantee graph connectivity among the evaluated methods.Connectivity is recorded as one when the search starting node can reach all other nodes.

H EXPERIMENTS ON TAOBAO DATA

On Taobao’s e-commerce data, NSG is evaluated against IVFPQ across dataset scales, including a 2-billion-vector dataset. The baseline cannot meet the response-time requirement at the largest scale, while NSG supports distributed search with daily updating.

  • NSG is 5–10 times faster than IVFPQ on the tested E10M and E45M datasets.IVFPQ is the original search engine baseline and meets the response-time requirement on those two scales.
  • IVFPQ cannot reach the response-time requirement on E2B, so its search time is not reported there.E2B contains 2 billion 128-dimensional vectors.
  • Distributed NSG search across partitions achieves about 5ms average response time at 98% precision.Searches run in parallel on multiple machines and their results are merged.
  • Each NSG partition takes about 12 hours to index, making daily updating possible.The large indexing time is addressed by building multiple NSGs on different subsets.

I EXPERIMENTS ON SEARCH AND INDEXING COMPLEXITY

The complexity experiments find that NSG search is close to logarithmic in dataset size and close to MRNG search complexity, while indexing follows an approximately N^1.3 pattern. Search complexity with K neighbors fits either a sublinear power law or a polylogarithmic law.

  • Search complexity: NSG’s search complexity on SIFT1M and GIST1M is approximately O(N^1/9.3 log N) and O(N^1/18.9 log N), respectively, for 1-NN and 100-NN search.The exponents 9.3 and 18.9 are close to the datasets’ intrinsic dimensions.
  • Search complexity: NSG’s search complexity is quite close to the MRNG’s O(cN^1/d/△r) complexity.Here, c is the MRNG’s average degree; the comparison concerns the theoretical search scaling.
  • Search complexity: The △r term is nearly constant on SIFT1M but scales about O(N^-1/18.9) on GIST1M, reflecting different data distributions.GIST vectors are denser and use real values from 0 to 1.5, whereas SIFT values are integers from 0 to 255.
  • Indexing complexity: NSG indexing combines approximate kNN construction, search-collect-select, and tree spanning, with search-collect-select identified as the most time-consuming part.The tree spanning step is usually about O(n), while approximate kNN construction depends on the chosen method.
  • Indexing complexity: The estimated indexing complexity is about O(εN^1+1/d), and the measured curves fit this form on both datasets.The estimate applies to the later NSG steps, including search-collect-select and tree spanning.
  • Scaling with K: K-NN search fits either O(K^0.46) or O((log K)^2.7), with differences attributed to hidden constant factors.Both forms fit the SIFT1M and GIST1M curves.

J PARAMETER TUNING

Parameter experiments identify dataset-dependent settings and evaluate how search and indexing scale with dataset size and requested neighbors. The reported curves remain close to logarithmic search growth and approximately N^1.3 indexing growth.

  • Parameter tuning: Optimal NSG parameters depend mainly on data distribution and change little as dataset scale increases.The paper recommends tuning parameters on a randomly sampled subset using grid search.
  • Search scaling: 1-NN search scales approximately O(N^1/9.3 log N) on SIFT1M and O(N^1/18.9 log N) on GIST1M.These complexities are slightly higher than O(log N), and the exponents are close to the datasets’ intrinsic dimensions.
  • Search scaling: 100-NN search shows the same approximate dataset-size scaling as 1-NN search on SIFT1M and GIST1M.The corresponding exponents are 9.3 for SIFT1M and 18.9 for GIST1M.
  • Search scaling: K-NN search scales approximately O(K^0.46) or O(log^2.7 K) on both datasets.The two fitted forms differ in their hidden constant factors.
  • Indexing scaling: NSG indexing complexity is approximately O(N^1+1/9.3 log N) on SIFT1M and O(N^1+1/18.9 log N) on GIST1M, close to O(N^1.3).The exponents 9.3 and 18.9 are close to the respective intrinsic dimensions.
Loading 1707.00143v10…