Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read CRouting estimates neighbor–query distances with a single dataset-derived angle in the cosine theorem, pruning up to 41.5% of distance calls on HNSW and NSG without losing recall.

desk verdict A clean, honestly-reported pruning plugin for HNSW/NSG; the gains are real on the tested data, but post hoc threshold selection and an unverified recovery mechanism keep the generality claims from being fully established. read the letter →

arxiv 2509.00365 v1 pith:RQF5IQJO submitted 2025-08-30 cs.DB cs.IR

Zhenxin Li , Shuibing He , Jiahao Guo , Xuechen Zhang , Xian-He Sun , Gang Chen This is my paper · ORCID
classification cs.DBcs.IR
keywords approximatenearestneighborsearchgraph-basedANNSdistancecomputationreductioncosinetheoremestimationangledistributionpruningstrategyerrorcorrectionHNSW/NSG
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the dominant cost in graph-based approximate nearest neighbor search is repeated exact distance computations, most spent on neighbors that never enter the candidate set. CRouting attacks this by estimating the distance from a neighbor to the query using two known distances and one fixed angle taken from the dataset's angle distribution, via the cosine theorem. If the estimate exceeds the current upper bound, the neighbor is pruned without an exact distance call; a revisit-based error-correction step then recomputes exact distances for pruned nodes that reappear through other graph paths. On HNSW and NSG over five datasets, the paper reports up to 41.5% fewer distance computations and up to 1.48x higher queries per second at matched recall, with construction time overhead under 4% and memory overhead of 2% to 21%. A sympathetic reader would care because CRouting is designed as a minimal-code plugin to two widely used graph indexes.

What carries the argument

The load-bearing object is the angle distribution of theta = angle(n, c, q), reduced to a single scalar: the 90th percentile of the dataset's measured angle values. CRouting replaces each exact distance call with a cosine-theorem estimate built from the stored edge length dist(c,n), the known dist(c,q), and that fixed representative angle. The error-correction pass rides on graph connectivity: a node pruned at one frontier is likely to be reached from another frontier, at which point its exact distance is computed before it is used.

What would settle it

On a given dataset and graph, measure the actual distribution of the routing angle along real search paths and compare it with the single fixed value CRouting uses; if the spread is wide, the estimate error grows. Then run CRouting with the 90th-percentile threshold on an anisotropic or strongly clustered dataset, for example synthetic mixtures of Gaussians with local directional structure, and compare its recall-QPS curve against exact greedy search: if recall at matched efS falls below the baseline, or if the fraction of wrongly pruned nodes that are never revisited exceeds the fraction rest

Watch

Extended reading notes

Core claim

The central claim is that the angle between the edge from the current node to a neighbor and the edge from the current node to the query concentrates around a dataset-specific value, so a single representative angle can stand in for every such angle in the cosine theorem. With the neighbor distance saved from graph construction and the current-node-to-query distance already known, the neighbor-to-query distance becomes a few arithmetic operations; if the estimate lies beyond the candidate set's upper bound, the neighbor is skipped. Because the estimate is approximate, CRouting marks pruned nodes and computes their exact distance if they are encountered again, betting that graph connectivity

Load-bearing premise

The method assumes that one fixed angle, measured from the dataset, is close enough to the real angle at every routing step that the cosine-theorem estimate prunes mostly useless neighbors, and that any useful neighbor it wrongly prunes will be reached again through another graph path.

Editorial extensions

If this is right

  • Distance-call speedups of 1.22x to 1.58x over HNSW and 1.15x to 1.71x over NSG at matched recall translate directly into QPS gains of up to 1.48x and 1.47x, making the method a drop-in accelerator for greedy-search-based graph indexes.
  • At 95% recall, CRouting cuts the time spent on negative-node distance calls by roughly 47% to 62%, and total search runtime by 12% to 31%, since the pruning check itself costs only a few multiply-add operations.
  • The plugin's overhead stays low: construction time rises by no more than 1% on HNSW and 4% on NSG, while index memory grows by 2% to 21%, with the ratio shrinking as dimensionality increases.
  • The reported gains hold across distance metrics (Euclidean, inner-product, cosine), across dataset sizes up to 100 million vectors, and across different graph-neighbor counts, with larger neighbor counts making the pruning opportunity larger.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The single-angle approximation is likely to be most reliable on graphs whose edges are built by diversity- or spread-out-promoting criteria; on graphs with strong directional hub structure, the actual per-node angle distribution may vary with node degree, so an extension would measure theta separately by degree class and use a per-class representative angle.
  • Because error correction only recovers pruned nodes that are revisited through other paths, datasets with weak connectivity or very small candidate-queue limits could see recall loss at aggressive pruning; an adaptive threshold tied to efS or candidate-queue size is a natural testable extension.
  • The 90th-percentile threshold is chosen empirically; the paper's own framework could support a tunable accuracy-latency budget by treating the angle as a continuous knob and precomputing the trade-off curve between pruning ratio and revisit cost for a given dataset.
  • CRouting's scalar estimate could serve as a cheap coarse pre-filter in front of more expensive estimators, such as residual-vector or LSH-based distance decompositions, reducing the number of times those heavier estimators must run.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes CRouting, a plugin for graph-based approximate nearest neighbor search (HNSW and NSG) that avoids many exact distance computations during greedy search. The idea is to estimate dist(n,q) with the cosine theorem using the already-known dist(c,q) and stored dist(c,n), substituting a fixed representative angle θ (the 90th percentile of a measured angle distribution) for the actual angle ∠ncq. Nodes whose estimated distance is not below the current upper bound are pruned; a subsequent error-correction step recomputes exact distances if a pruned node is encountered again via another path. The paper reports up to a 41.5% reduction in distance calls, QPS gains up to 1.48x, construction overhead below 4%, and memory overhead of 2-21% on five public datasets. The code is publicly available.

Significance. If the reported gains hold beyond the specific configuration tested, CRouting would be a practical, low-overhead drop-in optimization for two widely used graph indexes. The paper has clear strengths: it compares against two routing baselines (TOGG and FINGER), includes an ablation isolating the pruning and error-correction components (CRouting_O vs CRouting), reports construction time and index-size overhead, and evaluates generality across distance metrics and dataset scales. The main claims are internally consistent: the 1.71x distance-call speedup corresponds to a 41.5% reduction. However, the central accuracy claim depends on a parameter (θ percentile) that is selected post hoc on the same benchmark datasets, and on an unmeasured revisit-recovery mechanism. The paper explicitly acknowledges at §5.4 that no approximation error bound is proved. These load-bearing gaps need to be addressed before the results can be considered established.

major comments (3)
  1. [§5.5, Figure 13] The pruning threshold θ is a free parameter, and the paper selects the 90th percentile because it gives the best recall-QPS curves on the same five datasets used in the headline evaluation. This is a post hoc selection on the test bed: the reported 41.5% distance-call reduction and up to 1.48x QPS are therefore not independent predictions for those datasets. In addition, Figure 13 shows only the GIST dataset, while §5.5 states the 90th percentile is consistently best 'across all datasets and algorithms' without showing the supporting curves. The paper should either fix θ by an a-priori rule (e.g., based on dimensionality) or evaluate on a calibration split, and should report the sensitivity grid for all datasets.
  2. [§5.4, §4.2, Table 3] The final recall of CRouting rests entirely on the error-correction mechanism, but the paper provides no direct evidence that incorrectly pruned positive nodes are actually revisited and reinserted. Table 3 shows that pruning alone (CRouting_O) collapses recall from 0.978 to 0.453 at efs=100, and CRouting recovers only to 0.917, not to the 0.978 baseline. §5.4 reports relative error and incorrect-pruning ratios (max 5.83%) but does not measure how many of those incorrectly pruned nodes are later reached through alternative paths, which is the key assumption of Figure 1. Without a revisit-rate measurement or an oracle experiment, the claim that 'the same accuracy' is maintained is not established. Add a direct metric: fraction of pruned positive nodes later visited and inserted into the candidate set, and an ablation that compares against an oracle that never prunes positives.
  3. [§3.3, §4.2] The theoretical motivation assumes 'the position of neighbor n is completely random with respect to the current node c,' so that ∠ncq follows the near-orthogonal random-vector distribution. This is not consistent with how proximity graphs are built: neighbors are selected precisely because they are close to c, and the nodes that matter for the search (positive nodes) are biased toward small angles, as the paper's own Figure 9 and Table 3 demonstrate. The fixed-angle estimate is therefore systematically biased for exactly the nodes where pruning decisions matter. The paper should either frame the angle concentration as an empirical observation only, or analyze the conditional angle distribution for decision-relevant nodes and show that the representative angle remains safe under different graph densities and query distributions.
minor comments (5)
  1. [§5.1] The 'speedup in distance calls' is defined as the ratio to the brute-force method, but the experiments compare against vanilla HNSW/NSG, not brute force. Please clarify the baseline in the definition.
  2. [Figure 7 caption] Caption reads 'HSNW' for HNSW; please fix the typo.
  3. [§5.5 heading] The section heading 'Sensitive Analysis' should be 'Sensitivity Analysis'.
  4. [§4.3] The formula IPDist(c,q) = 1 - ||c||||q||cosθ is unconventional. If this is the definition used in the implementation, please define it explicitly and state how it relates to standard inner-product distance on unnormalized vectors.
  5. [§3.3] The sentence 'the angle distribution is solely determined by the dimensionality' refers to the random-vector density in Eq. (3), but the subsequent argument correctly notes that the search-path angle distribution depends on the dataset. Please rephrase to avoid the apparent contradiction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; CRouting's speedup is an empirical, tuned result, not a derivation that reduces to its inputs.

full rationale

CRouting's claimed derivation chain is: observe that angles ∠ncq concentrate around a dataset-specific value, use that fixed θ in the cosine theorem to estimate dist(n,q), prune when the estimate exceeds the upper bound, and rely on graph connectivity to revisit wrongly pruned nodes. At no point is the output defined as the input: the angle distribution is measured from sample searches (§4.1), the 90th-percentile θ is selected in §5.5 from recall-QPS curves, and the reported speedup is then measured on the benchmarks. This is hyperparameter tuning on evaluation data, which is a legitimate generalization concern but not a logical circularity (there is no equation in which the predicted quantity is identical to the fit input). The paper also explicitly disclaims analytic error bounds (§5.4) and does not measure the revisit-recovery rate, but these are correctness/robustness limitations, not examples of self-definition, fitted-input-called-prediction, or self-citation load-bearing. No load-bearing self-citations or imported uniqueness theorems are present.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim rests on an empirically measured angle distribution, a tuned pruning threshold, and a heuristic connectivity assumption. No new physical or mathematical entities are introduced.

free parameters (2)
  • Pruning threshold percentile (theta percentile) = 90th percentile of the dataset's measured angle distribution
    Chosen post hoc in §5.5 after inspecting recall-QPS curves across all datasets and algorithms; the paper reports 90th percentile was consistently best and sets this for all headline results.
  • Angle sampling ratio n_sample = 0.1% of dataset size
    Default set in §4.1; arbitrary design choice that affects the measured angle distribution and construction overhead, but not tuned against the target metric.
assumptions (5)
  • standard math High-dimensional random vectors are almost orthogonal (Equation 3)
    Used in §3.3 to motivate that random-vector angles concentrate near pi/2; cited to [9].
  • domain assumption The direction of a neighbor n relative to current node c is random enough that angle n-c-q follows a distribution similar to random vectors
    Stated in §3.3 ('the position of neighbor n is completely random with respect to the current node c'); approximated empirically in Figures 7 and 8, but not proven.
  • domain assumption The angle distribution is an intrinsic property of the dataset and stable across query sets
    Claimed from Figure 8 observations (§3.3); used to justify measuring once with 0.1% sample queries and reusing the result indefinitely.
  • domain assumption Mistakenly pruned nodes will be revisited through alternative graph paths, enabling error correction
    Core of the error-correction mechanism in §4.2; argued by example (Figure 1) with no guarantee for general graphs.
  • domain assumption Stored neighbor distances dist(c,n) from construction remain valid and accessible at query time
    Assumed in §4.1; requires storing edge distances (2-21% memory overhead) and a static graph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/RQF5IQJO

@misc{pith2026250900365,
  author       = {Pith},
  title        = {Pith review of: CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQF5IQJO}},
  note         = {Machine review of arXiv:2509.00365}
}
abstract

Approximate nearest neighbor search (ANNS) is a crucial problem in information retrieval and AI applications. Recently, there has been a surge of interest in graph-based ANNS algorithms due to their superior efficiency and accuracy. However, the repeated computation of distances in high-dimensional spaces constitutes the primary time cost of graph-based methods. To accelerate the search, we propose a novel routing strategy named CRouting, which bypasses unnecessary distance computations by exploiting the angle distributions of high-dimensional vectors. CRouting is designed as a plugin to optimize existing graph-based search with minimal code modifications. Our experiments show that CRouting reduces the number of distance computations by up to 41.5% and boosts queries per second by up to 1.48$\times$ on two predominant graph indexes, HNSW and NSG. Code is publicly available at https://github.com/ISCS-ZJU/CRouting.

Figures

Figures reproduced from arXiv: 2509.00365 by the authors.

Figure 1
Figure 1. Illustration of the greedy search algorithm. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Running time analysis of the greedy search across [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 5
Figure 5. Triangle formed by the current search node [PITH_FULL_IMAGE:figures/full_fig_p003_5.png] view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: Decomposition of the distance computation in FIN [PITH_FULL_IMAGE:figures/full_fig_p003_4.png]
Figure 7
Figure 7. Figure 7: Probability density of angles on HSNW and NSG algorithms. The number of queries is 0.1% of the dataset size. [PITH_FULL_IMAGE:figures/full_fig_p004_7.png]
Figure 8
Figure 8. Figure 8: Probability density of angles on HNSW algorithm. The number of queries varies from 0.1% to 100% of the dataset size. [PITH_FULL_IMAGE:figures/full_fig_p004_8.png]
Figure 9
Figure 9. Figure 9: Example of incorrect estimation. Extra time overhead. By default, the value of 𝑛𝑠𝑎𝑚𝑝𝑙𝑒 is set to 0.1% of the number of nodes used to construct the graph. Because the sampling frequency is sufficient to obtain an accurate angle distribution (as shown in [PITH_FULL_IMAG…
Figure 10
Figure 10. Figure 10: Recall-QPS curves (the top right is better). [PITH_FULL_IMAGE:figures/full_fig_p007_10.png]
Figure 11
Figure 11. Figure 11: Recall-speedup curves (the top right is better). [PITH_FULL_IMAGE:figures/full_fig_p007_11.png]
Figure 12
Figure 12. Figure 12: Time cost breakdown. On each dataset, the bar [PITH_FULL_IMAGE:figures/full_fig_p007_12.png]
Figure 13
Figure 13. Figure 13: Effect of the pruning threshold. accuracy is acceptable [PITH_FULL_IMAGE:figures/full_fig_p008_13.png]
Figure 14
Figure 14. Figure 14: Effect of the number of connected neighbors. [PITH_FULL_IMAGE:figures/full_fig_p009_14.png]
Figure 16
Figure 16. Figure 16: Generality across different distance metrics. [PITH_FULL_IMAGE:figures/full_fig_p009_16.png]
Figure 17
Figure 17. Figure 17: Scalability across different data volumes. [PITH_FULL_IMAGE:figures/full_fig_p009_17.png]
Figure 18
Figure 18. Figure 18: Recall-QPS curves for various routing strategies (the top right is better). [PITH_FULL_IMAGE:figures/full_fig_p010_18.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. HNSW with Accuracy Guarantees Using Graph Spanners

    cs.DB 2026-07 unverdicted novelty 7.0 of 10

    A tiered Certify-then-Rectify system for HNSW that certifies approximate results statistically and falls back to exact recovery by treating the graph as a spanner whose stretch is bounded via extreme value theory.

Reference graph

Works this paper leans on

87 extracted references · 63 canonical work pages · cited by 1 Pith paper

  1. [1]

    Anon. 2010. Datasets for approximate nearest neighbor search. http://corpus- texmex.irisa.fr/. Last accessed on Sep-2024

    2010

  2. [2]

    Anon. 2011. Million Song Dataset Benchmarks. http://www.ifs.tuwien.ac.at/mir/ msd/. Last accessed on Sep-2024

    2011

  3. [3]

    Anon. 2018. Deep1M Dataset. https://www.cse.cuhk.edu.hk/systems/hash/gqr/ datasets.html. Last accessed on Sep-2024

    2018

  4. [4]

    Matej Antol, Jaroslav Ol’ha, Terézia Slanináková, and Vlastislav Dohnal. 2021. Learned metric index—proposition of learned indexing for unstructured data. Information Systems 100 (2021), 101774

    2021

  5. [5]

    Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. Hd- index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. arXiv preprint arXiv:1804.06829 (2018)

    arXiv 2018

  6. [6]

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374

    2020

  7. [7]

    Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 931–938

    2014

  8. [8]

    Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence 37, 6 (2014), 1247–1260

    2014

Show all 87 references
  1. [9]

    Keith Ball et al. 1997. An elementary introduction to modern convex geometry. Flavors of geometry 31, 1-58 (1997), 26

    1997

  2. [10]

    Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. 2019. Learning to route in similarity graphs. In International Conference on Machine Learning. PMLR, 475–484

    2019

  3. [11]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517

    1975

  4. [12]

    Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning. 97–104

    2006

  5. [13]

    Leonid Boytsov and Bilegsaikhan Naidan. 2013. Engineering efficient and effective non-metric space library. In Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings 6 . Springer, 280–293

    2013

  6. [14]

    Moses S Charikar. 2002. Similarity estimation techniques from rounding algo- rithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. 380–388

    2002

  7. [15]

    Patrick Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2023. Finger: Fast inference for graph-based approximate nearest neighbor search. In Proceedings of the ACM Web Conference 2023 . 3225– 3235

    2023

  8. [16]

    Paolo Ciaccia, Marco Patella, Pavel Zezula, et al. 1997. M-tree: An efficient access method for similarity search in metric spaces. In Vldb, Vol. 97. Citeseer, 426–435

    1997

  9. [17]

    CXL Consortium. 2020. Cxl specification. https://computeexpresslink.org/cxl- specification/. Last accessed on Sep-2024

    2020

  10. [18]

    Ryan R Curtin, Parikshit Ram, and Alexander G Gray. 2013. Fast exact max-kernel search. In Proceedings of the 2013 SIAM International Conference on Data Mining . SIAM, 1–9

    2013

  11. [19]

    Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 537–546

    2008

  12. [20]

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality- sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry . 253–262

    2004

  13. [21]

    Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. 2020. Learning Space Partitions for Nearest Neighbor Search. In International Conference on Learning Representations

    2020

  14. [22]

    Karima Echihabi, Kostas Zoumpatianos, and Themis Palpanas. 2021. New trends in high-d vector similarity search: al-driven, progressive, and distributed. Pro- ceedings of the VLDB Endowment 14, 12 (2021), 3198–3201

    2021

  15. [23]

    Chao Feng, Defu Lian, Xiting Wang, Zheng Liu, Xing Xie, and Enhong Chen

  16. [24]

    Myron Flickner, Harpreet Sawhney, Wayne Niblack, Jonathan Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, et al. 1995. Query by image and video content: The QBIC system. computer 28, 9 (1995), 23–32

    1995

  17. [25]

    Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 4139–4150

    2021

  18. [26]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment 12, 5 (2019), 461–474

    2019

  19. [27]

    Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In Proceedings of the 2012 11 Conference’17, July 2017, Washington, DC, USA Li et al. ACM SIGMOD international conference on management of data . 541–552

    2012

  20. [28]

    Jianyang Gao and Cheng Long. 2023. High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–27

    2023

  21. [29]

    Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27

    2024

  22. [30]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence 36, 4 (2013), 744–755

    2013

  23. [31]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE conference on computer vision and pattern recognition . 2946–2953

    2013

  24. [32]

    Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premku- mar Srinivasan, et al. 2023. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In P...

    2023

  25. [33]

    Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. 2020. iDEC: indexable distance estimating codes for approximate nearest neighbor search. Proceedings of the VLDB Endowment 13, 9 (2020)

    2020

  26. [34]

    Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2012. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE transactions on pattern analysis and machine intelligence 35, 12 (2012), 2916–2929

    2012

  27. [35]

    Adrien Grand. 2023. Vector search in Elasticsearch: The rationale behind the design. https://www.elastic.co/search-labs/blog/vector-search-elasticsearch- rationale. Last accessed on Sep-2024

    2023

  28. [36]

    Fabian Groh, Lukas Ruppert, Patrick Wieschollek, and Hendrik PA Lensch. 2022. Ggnn: Graph-based gpu nearest neighbor search. IEEE Transactions on Big Data 9, 1 (2022), 267–279

    2022

  29. [37]

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning. PMLR, 3887–3896

    2020

  30. [38]

    Gaurav Gupta, Tharun Medini, Anshumali Shrivastava, and Alexander J Smola

  31. [39]

    Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 5713–5722

    2016

  32. [40]

    Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search. Proceedings of the VLDB Endowment 9, 1 (2015), 1–12

    2015

  33. [41]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing . 604–613

    1998

  34. [42]

    J Jang, H Choi, H Bae, S Lee, M Kwon, and M Jung. 2023. CXL-ANNS: Software- Hardware Collaborative Memory Disaggregation and Computation for Billion- Scale Approximate Nearest Neighbor Search. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). USENIX Association

    2023

  35. [43]

    Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128

    2010

  36. [44]

    Wenqi Jiang, Shigang Li, Yu Zhu, Johannes de Fine Licht, Zhenhao He, Runbin Shi, Cedric Renggli, Shuai Zhang, Theodoros Rekatsinas, Torsten Hoefler, et al

  37. [45]

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535–547

    2019

  38. [46]

    Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. 1998. The MNIST Database of Handwritten Digits. http://yann.lecun.com/exdb/mnist/. Last accessed on Sep-2024

    1998

  39. [47]

    In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

    Co-design hardware and algorithm for vector search. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15

  40. [48]

    Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. 2020. Improving approximate nearest neighbor search through learned adaptive early termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2539–2554

    2020

  41. [49]

    Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The design and implementation of a real time visual search system on JD E-commerce platform. In Proceedings of the 19th International Middleware Conference Industry. 9–16

    2018

  42. [50]

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing S...

    2020

  43. [51]

    Lingli Li, Ao Han, Xiaotong Cui, and Baohua Wu. 2024. Flex: a fast and light- weight learned index for KNN search in high-dimensional space. Information Sciences 669 (2024), 120546

    2024

  44. [52]

    Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2019), 1475–1488

    2019

  45. [53]

    Jinfeng Li, Xiao Yan, Jian Zhang, An Xu, James Cheng, Jie Liu, Kelvin KW Ng, and Ti-chung Cheng. 2018. A general and efficient querying method for learning to hash. In Proceedings of the 2018 International Conference on Management of Data. 1333–1347

    2018

  46. [54]

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov

  47. [55]

    Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836

    2018

  48. [56]

    Kejing Lu, Hongya Wang, Wei Wang, and Mineichi Kudo. 2020. VHP: approximate nearest neighbor search via virtual hypersphere partitioning. Proceedings of the VLDB Endowment 13, 9 (2020), 1443–1455

    2020

  49. [57]

    Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 2227–2240

    2014

  50. [58]

    Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres

  51. [59]

    Intel Newsroom. 2019. Intel ® OptaneTM DC Persistent Memory. https://www.intel.com/content/www/us/en/products/memory-storage/optane- dc-persistent-memory.html. Last accessed on Sep-2024

    2019

  52. [60]

    Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Umar Farooq Minhas, Jeffery Pound, Cedric Renggli, Nima Reyhani, Ihab F Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2024. Incremental IVF Index Maintenance for Streaming Vector Search. arXiv preprint arXiv:2411...

    2024 arXiv

  53. [61]

    Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning. PMLR, 7803–7813

    2020

  54. [62]

    Jianbin Qin, Wei Wang, Chuan Xiao, Ying Zhang, and Yaoshu Wang. 2021. High- dimensional similarity query processing for data science. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 4062–4063

    2021

  55. [63]

    Parikshit Ram and Kaushik Sinha. 2019. Revisiting kd-tree for nearest neighbor search. In Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining . 1378–1388

    2019

  56. [64]

    Jie Ren, Minjia Zhang, and Dong Li. 2020. Hm-ann: Efficient billion-point nearest neighbor search on heterogeneous memory. Advances in Neural Information Processing Systems 33 (2020), 10672–10684

    2020

  57. [65]

    Marco Patella and Paolo Ciaccia. 2009. Approximate similarity search: A multi- faceted problem. Journal of Discrete Algorithms 7, 1 (2009), 36–48

    2009

  58. [66]

    Zhitao Shen, Shiyu Yang, Weibo Chen, Kunming Wang, Yue Li, Jiabao Jin, Wei Jia, Junwei Chen, Yuan Su, Xiaoxia Duan, Wei Chen, Lei Wang, Jie Song, Ruoyi Ruan, and Xuemin Lin. 2025. TierBase: A Workload-Driven Cost-Optimized Key-Value Store . In 2025 IEEE 41st International Conf...

    2025

  59. [67]

    Chanop Silpa-Anan and Richard Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1–8

    2008

  60. [68]

    Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Har- sha Vardhan Simhadri. 2021. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search. arXiv preprint arXiv:2105.09613 (2021)

    2021 arXiv

  61. [69]

    Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Kr- ishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: fast accurate billion- point nearest neighbor search on a single node. In Proceedings of the 33rd Inter- national Conference on Neural Information Processi...

    2019

  62. [70]

    Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web. 285–295

    2001

  63. [71]

    Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2010. Efficient and accu- rate nearest neighbor and closest pair search in high-dimensional space. ACM Transactions on Database Systems (TODS) 35, 3 (2010), 1–46

    2010

  64. [72]

    Yao Tian, Ziyang Yue, Ruiyuan Zhang, Xi Zhao, Bolong Zheng, and Xiaofang Zhou. 2023. Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions. IEEE Data Eng. Bull. 46, 3 (2023), 39–54

    2023

  65. [73]

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xi- angyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 International Conference on Management of Data . 2614–...

    2021

  66. [74]

    Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2024. An efficient and robust framework for approximate near- est neighbor search with attribute constraint. Advances in Neural Information Processing Systems 36 (2024)

    2024

  67. [75]

    Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. Proceedings of the VLDB Endowment (2014)

    2014

  68. [76]

    Xiaoliang Xu, Mengzhao Wang, Yuxiang Wang, and Dingcheng Ma. 2021. Two- stage routing with optimized guided search and greedy algorithm on proximity graph. Knowledge-Based Systems 229 (2021), 107305

    2021

  69. [77]

    Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In Proceedings of the 29th Symposium on Operating Systems Principles. 545–561

    2023

  70. [78]

    Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-high- dimensional approximate nearest neighbor search extension. InProceedings of the 2020 ACM SIGMOD international conference on management of data . 2241–2253

    2020

  71. [79]

    Weijie Zhao, Shulong Tan, and Ping Li. 2020. Song: Approximate nearest neighbor search on gpu. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1033–1044

    2020

  72. [80]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A com- prehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment 14, 11 (2021), 1964–1978

    2021

  73. [81]

    Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, et al. 2025. VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search.arXiv preprint arXiv:2503.17911 (2025)

    2025 arXiv

  74. [82]

    Chun Jiang Zhu, Tan Zhu, Haining Li, Jinbo Bi, and Minghu Song. 2019. Accel- erating large-scale molecular similarity search through exploiting high perfor- mance computing. In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 330–333. 13

    2019

  75. [85]

    Bolong Zheng, Zhao Xi, Lianggui Weng, Nguyen Quoc Viet Hung, Hang Liu, and Christian S Jensen. 2020. PM-LSH: A fast and accurate LSH framework for high-dimensional approximate NN search. Proceedings of the VLDB Endowment 13, 5 (2020), 643–655

    2020

  76. [2014]

    Information Systems 45 (2014), 61–68

    Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68

    2014

  77. [2019]

    Pattern Recognition 96 (2019), 106970

    Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition 96 (2019), 106970

    2019

  78. [2022]

    In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

    Bliss: A billion scale index using iterative re-partitioning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . 486–495

  79. [2023]

    ACM Transactions on Information Systems 41, 1 (2023), 1–27

    Reinforcement routing on proximity graph for efficient recommendation. ACM Transactions on Information Systems 41, 1 (2023), 1–27

    2023

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.