Pith. sign in

REVIEW 7 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1707.00143 v10 pith:EUHXF4W6 submitted 2017-07-01 cs.LG

Cong Fu , Chao Xiang , Changxu Wang , Deng Cai This is my paper · ORCID
classification cs.LG
keywords graphsearchcomplexityannsbillion-nodefastgraph-basedindexing
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 7 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 25 citations worldwide. Full citation record

  1. Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

    cs.DB 2026-07 conditional novelty 6.0 of 10

    CHAT uses HNSW-specific monotonic and unimodal structure plus resource surrogates to tune M, efc, and efs under constraints, beating black-box tuners by up to 45% throughput or 11% recall and up to 44× faster convergence.

  2. Fast Approximate Vector Joins via Offline-Online Co-Design

    cs.DB 2026-03 conditional novelty 6.0 of 10

    A merged index and soft work sharing speed up approximate threshold-based vector joins by up to 56x, with a hybrid search improving out-of-distribution recall by up to 43%.

  3. Cross-View Localization via Redundant Sliced Observations and A-Contrario Validation

    cs.CV 2025-08 conditional novelty 6.0 of 10

    Slice-Loc divides panoramic query images into slices, estimates each slice's 3-DoF pose, and uses an a-contrario false-alarm model to reject unreliable localizations, cutting DReSS cross-area mean error from 4.47 m to 1.86 m.

  4. SIEVE: Effective Filtered Vector Search with Collection of Indexes

    cs.DB 2025-07 conditional novelty 6.0 of 10

    SIEVE builds a workload-aware collection of small HNSW subindexes and uses a cost model to pick the best one per query, speeding up filtered vector search up to 8.06x versus prior graph-based methods.

  5. DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search

    cs.DB 2025-05 reject novelty 6.0 of 10

    DARTH learns to predict a query's current recall during HNSW/IVF search and stops early at a user-specified target, achieving speedups up to 14.6x on HNSW and 41.8x on IVF, yet 13-15% of queries miss the target.

  6. OrchANN: Hierarchical Orchestration for Skewed Out-of-Core Vector Search

    cs.DB 2025-12 conditional novelty 5.5 of 10

    OrchANN's unified I/O orchestration—hybrid per-cluster indexes, query-driven routing graphs, and triangle-inequality pruning—cuts SSD reads and outperforms DiskANN, Starling, SPANN, and PipeANN in out-of-core vector search.

  7. Filtered Approximate Nearest Neighbor Search: A Unified Benchmark and Systematic Experimental Study [Experiment, Analysis & Benchmark]

    cs.DB 2025-09 conditional novelty 5.0 of 10

    A systematic benchmark of filtered nearest-neighbor search algorithms shows no single winner: filter-then-search methods excel at containment and equality filters, while hybrid methods dominate overlap filters.

Pith tools