Pith. sign in

REVIEW 4 major objections 6 minor 72 references

Efficient Graph-Based Approximate Nearest Neighbor Search Achieving: Low Latency Without Throughput Loss

T0 review · 4 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read AverSearch claims that replacing fork-join parallelism with a fully asynchronous pipeline lets a graph ANNS engine cut latency without losing throughput, reporting up to 8.93x higher QPS at matching latency than iQAN.

desk verdict A genuinely novel asynchronous design for intra-query parallel graph ANNS, but the title overclaims and the missing drift bound plus no artifact keep it from being fully convincing. read the letter →

arxiv 2504.20461 v2 pith:PN3JUF6V submitted 2025-04-29 cs.DC

Jingjia Luo , Mingxing Zhang , Kang Chen , Xia Liao , Yingdi Shan , Jinlei Jiang , Yongwei Wu This is my paper · ORCID
classification cs.DC
keywords approximatenearestneighborsearchgraph-basedintra-queryparallelismasynchronousarchitecturememorybandwidthworkstealingquerylatencythroughput
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 argues that the traditional fork-join model of intra-query parallelism is the reason graph-based approximate nearest neighbor search cannot be both low-latency and high-throughput: synchronization barriers leave memory bandwidth idle, and fixed-width speculative expansion recomputes vertices that serial search would prune. To test this, it builds AverSearch, which decomposes best-first search into three asynchronous roles—sub-queue maintainers, distance calculators, and a global balancer—that communicate through a shared distance array and an approximate L-threshold rather than barriers. On six datasets the system reports higher throughput than the leading parallel ANNS engine at the same parallelism settings, and 2.17x to 8.93x higher throughput at comparable latency, with 1.54x to 1.96x lower minimum average latency. A sympathetic reader would take this as evidence that latency and throughput are not necessarily in conflict for CPU-based ANNS, and that the conflict is an artifact of the parallel execution model rather than of graph search itself.

What carries the argument

The central mechanism is the fully asynchronous decomposition of Best-First Search into three thread roles plus two shared structures. The distance array stores each computed query-vertex distance with a 'ready' flag so calculators and maintainers never hand data to each other directly; the approximate L-threshold, computed by a global balancer from stale sub-queue snapshots, lets maintainers prune without a global barrier. Its job is to keep distance-calculation threads continuously fed, raising effective memory bandwidth, and to prune only what serial search would also prune, lowering the redundant expansion ratio.

What would settle it

Run AverSearch against iQAN at the same 24x2 configuration on a dataset engineered to have many near-tie distances around the pruning boundary and check recall@100 at matched latency: if recall drops below iQAN's, or if the shared 'ready'-flag misses cause duplicate distance computations on a 128D dataset, the claim that the async design loses no throughput at equal accuracy fails.

Watch

Extended reading notes

Core claim

Stated on its own terms, the discovery is that parallel graph ANNS can be made fully asynchronous by replacing the global priority queue with per-subgroup sub-queues, letting each query's worker threads play three non-blocking roles. The sub-queue maintainer owns ordered candidates; distance calculators pull vertices and write distances to a shared distance array with ready flags, speculatively moving to the next unchecked vertex when the queue has not changed; a global balancer announces a slightly larger approximate L-threshold from asynchronous snapshots and steers pruning and work-stealing. Because no thread waits on a join, physical memory bandwidth stays high, and because the threshold and work-stealing are dynamic, the fraction of redundant expansions falls. The paper claims that AverSearch consistently beats iQAN on both throughput and latency under identical parallelism, reaching 8.93x higher throughput at comparable latency on DEEP100M and cutting minimum average latency by up to 1.96x.

Load-bearing premise

The load-bearing premise is that the approximate L-threshold, computed from stale asynchronous snapshots of the sub-queues, stays close enough to the true global order that pruning never discards vertices a serial search would expand; the paper offers no bound on that drift.

Editorial extensions

If this is right

  • Under identical parallelism settings, AverSearch reports 1.23x-2.38x higher QPS than iQAN on SIFT100M and DEEP100M with 1.07x-2.35x lower latency, so the async design dominates on both axes for the same thread allocation.
  • At comparable latency (within 20 percent), the reported throughput advantage is 2.17x on SE-OpenAI and up to 8.93x on DEEP100M, meaning the entire QPS-latency frontier shifts outward.
  • Minimum average latency drops by 1.54x-1.96x across datasets, which is the metric that matters for RAG responses that issue multiple retrieval rounds and for attention-based retrieval.
  • Against FAISS and Milvus, the system reports up to 9.82x lower latency and up to 5.68x higher throughput at high recall, suggesting production vector databases could adopt the asynchronous search path.
  • The pipeline is graph-agnostic in the experiments: it runs on NSG, SSG, and Vamana indexes and inside a FAISS integration, so the gain is not tied to one index structure.

Reading between the lines

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

  • Not claimed by the paper, but a natural generalization: the same three-role split (queue maintainer, distance calculator, global balancer) could be applied to other memory-bound priority-queue graph algorithms such as Dijkstra's shortest paths or personalized PageRank, where fork-join barriers create the same idle-bandwidth problem.
  • The paper does not bound how far the approximate L-threshold drifts from the global order; a follow-up could instrument snapshot age against recall on a dataset with tight distance clusters to see whether the pruning slack can be reduced without hurting quality.
  • The paper notes that static role assignment keeps low-dimensional datasets from reaching peak memory bandwidth; an adaptive scheme that lets idle distance calculators take over sub-queue maintenance when a queue drains is a plausible next step.
  • For per-token attention retrieval in long-context inference, the paper's own data emphasize the 1.54x-1.96x minimum-latency reduction as the primary benefit, since those workloads query serially many times rather than maximize concurrent QPS.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper presents AverSearch, a CPU-based graph ANNS engine built on a fully asynchronous architecture. It decomposes each query into sub-queue maintainer threads, distance calculator threads, and a global balancer thread, and uses shared lock-free distance arrays, an approximate L-threshold, and work stealing to reduce synchronization and redundant computation. The authors claim that AverSearch consistently achieves higher throughput and lower latency than iQAN under the same intra-query/inter-query parallelism settings, with up to 2.1x-8.9x higher throughput at comparable latency and 1.5x-1.9x lower minimum average latency across six datasets, including 100M-vector and high-dimensional embedding datasets. The evaluation also reports PMB and redundancy-ratio measurements, a breakdown analysis, a FAISS integration, and comparisons with Milvus, ParlayANN, and quantization baselines.

Significance. If the central empirical claims hold, AverSearch is a practically significant contribution to intra-query parallel graph-based ANNS: it addresses a real limitation of fork-join engines by keeping memory-intensive distance computation continuously busy, and the main comparison against iQAN is carried out on shared NSG and Vamana indices, which is a credible experimental design. The paper deserves credit for reporting physical memory bandwidth via hardware counters, for decomposing CPU time into expand/sync/redundant/serial components, and for providing an ablation that separates the asynchronous architecture from work stealing and inlining. The paper also candidly notes limitations in §5.3, including that PMB does not always reach the machine maximum on short-vector datasets and that RR is comparable to iQAN on the two small Simple English datasets. However, the headline claim 'low latency without throughput loss' is stronger than the evidence, and the approximate L-threshold used by the asynchronous design has no correctness guarantee, so the recall-matched QPS advantage could be a partial artifact of over-pruning on unseen datasets.

major comments (4)
  1. [§4.2, Algorithms 3–5] The approximate L-threshold computed in Algorithm 3 from asynchronous sub-queue snapshots has no correctness bound. The balancer simulates pruning based only on the vertices currently visible in the sub-queues, while Algorithm 5 can write distances into the distance array that Algorithm 4 has not yet merged into any sub-queue. If such in-flight vertices are farther than the current threshold, the announced threshold can be strictly below the exact L-th nearest distance among all vertices discovered so far, and Algorithm 4 line 11 can permanently prune candidates that serial BFiS would expand. Since recall@100 is a measured outcome rather than an invariant, the reported QPS gains at fixed recall could partly reflect over-pruning, and the result may not transfer to datasets with different distance distributions. Please provide either a formal drift bound on the approximate threshold relative to the exact L-th order, or an empirical sensitivity study (for example, recall and QPS as functions of threshold-update frequency and snapshot staleness), and consider releasing the implementation for independent verification.
  2. [Title, Abstract, and §5.2 (Figures 1 and 10)] The claim 'low latency without throughput loss' is stronger than the data support. In Figures 1 and 10, AverSearch's own QPS decreases as intra-query parallelism increases, for example in the SIFT100M and Wiki100M panels at recall 0.90 and 0.995; the plotted configurations move left toward lower latency and downward in QPS as the intra-thread count grows. What the evaluation actually supports is that AverSearch dominates iQAN at the same parallelism configurations and achieves higher QPS at comparable latency. The title and the corresponding abstract/conclusion sentences should be revised to state the relative comparison precisely rather than implying that latency can be reduced with no throughput cost in absolute terms.
  3. [§3.2 and Table 1] The throughput formula Throughput ∝ PMB × (1 − RR) is introduced as an empirical formula but is not validated as a quantitative model. Table 1 reports a 2.2× predicted EMB improvement on Wiki100M against a 1.78× measured throughput difference, and the PMB and RR ratios vary substantially across datasets, yet no residual analysis, fitted constant, or correlation statistic is provided. The qualitative narrative that asynchrony improves PMB and reduces RR is consistent with the measurements, but the formula should be presented as a heuristic explanation rather than a predictive relation, or it should be validated with explicit error bounds.
  4. [§5.1–§5.2] The evaluation does not report how search hyperparameters (L, entry-point selection, recall targets) were chosen for each system, nor the achieved recall values around each target. Recall@100 is used as a target, but without a tolerance band or per-configuration recall numbers, a reader cannot determine whether the QPS comparisons are exactly at matched quality; small recall differences can translate into large QPS differences. Please include achieved recall and the corresponding L values for each plotted configuration, or state explicitly how the target recall was enforced and verified for every data point.
minor comments (6)
  1. [§2.3.1] There is a typo in 'controling the search precision'; it should be 'controlling'.
  2. [§2.3.2] The phrase 'bellowing l3' should read 'below line 3'.
  3. [§4.3] The sentence 'Regarding dependency ➁' appears twice in consecutive paragraphs; the second occurrence should refer to the next dependency being disentangled for clarity.
  4. [Figures 3, 8, and 9] The role of the thread that maintains a sub-queue is referred to inconsistently as 'sub-que thread' and 'sub-queue maintainer'; please unify the terminology.
  5. [Algorithm 3] Algorithm 3 is presented as pseudocode, but its body only states the assignment of L-threshold; please provide the actual merge-simulation steps, including how often the balancer runs and what it does when a sub-queue is empty.
  6. [§5.4] The Milvus and FAISS comparisons are acknowledged as not head-to-head; consider presenting them in a clearly labeled auxiliary subsection so that they are not read as direct system benchmarks.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: headline QPS/latency gains are measured against external baselines on shared graphs; the EMB formula is a post-hoc explanatory heuristic, not a fitted input or self-citation.

full rationale

No significant circularity found. The paper's central performance claims are direct measurements against external baselines (iQAN, FAISS, Milvus, ParlayANN) on shared graphs with fixed total thread count, so the reported QPS and latency numbers are not derived from fitted parameters or from the authors' own prior results. The 'empirical formula' Throughput proportional to EMB = PMB x (1-RR) is introduced in Section 3.2 as a heuristic for reasoning about synchronization overhead and redundant computation, and it is checked against measured PMB/RR values in Section 5.3; it is not used to manufacture the headline QPS figures. The approximate L-threshold in Section 4.2 is an algorithmic approximation whose quality is a correctness/robustness concern rather than a circular derivation: its effect is validated by measured recall@100 against ground-truth neighbors, not guaranteed by construction. No self-citations are load-bearing; the paper cites external prior work such as iQAN, NSG, HNSW, and ParlayANN. The claimed gains are therefore self-contained empirical results.

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

No new physical or mathematical entities are postulated. New components (sub-queue maintainer, distance calculator, global balancer, distance array, L-threshold, EMB metric) are implementation structures, not independent entities with falsifiable handles outside the system.

free parameters (2)
  • search list length L = not stated numerically; set per dataset and recall target (0.9 to 0.995)
    L controls the quality-throughput operating point in Best-First Search. It is a tuned search hyperparameter, standard in ANNS benchmarking, and is used to match recall across systems; it is not fitted to produce a derived law.
  • intra/inter thread configuration = sweeps such as 1x48, 2x24, 4x12, 8x6, 16x3, 24x2 on 48 cores
    The paper sweeps the number of threads per query versus concurrent queries and plots the convex hull. This is a configuration choice that shapes the headline QPS-latency numbers.
assumptions (5)
  • domain assumption Best-First Search with a bounded priority queue of size L returns approximate top-K neighbors with controllable recall.
    The entire evaluation measures recall@100 as a function of L; the paper assumes BFiS quality depends on L in the standard way established by prior ANNS literature.
  • domain assumption The NSG and Vamana graphs used are searchable at the reported recall levels.
    Search quality depends on graph construction from prior work (NSG, SSG, ParlayANN, DiskANN); the paper builds these graphs with standard tooling and does not analyze how graph differences affect the comparative results.
  • ad hoc to paper Concurrent reads and writes to the shared distance array are benign in practice.
    Section 4.3 has distance calculators write the distance array without barriers while sub-queue maintainers read it; the paper relies on measured recall, not a correctness argument, to justify this race tolerance.
  • ad hoc to paper Throughput is approximately proportional to PMB times (1 minus RR).
    Section 3.2 states this as an empirical formula without derivation; it is used to attribute speedups and to justify the asynchronous design.
  • ad hoc to paper The approximate L-threshold computed from asynchronous sub-queue snapshots does not materially degrade recall.
    Section 4.2 describes the approximation; the paper does not bound the drift from the true L-th nearest distance, relying on recall measurements instead.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Graph-Based Approximate Nearest Neighbor Search Achieving: Low Latency Without Throughput Loss." pith.science (2026). https://pith.science/paper/PN3JUF6V

@misc{pith2026250420461,
  author       = {Pith},
  title        = {Pith review of: Efficient Graph-Based Approximate Nearest Neighbor Search Achieving: Low Latency Without Throughput Loss},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PN3JUF6V}},
  note         = {Machine review of arXiv:2504.20461}
}
read the original abstract

The increase in the dimensionality of neural embedding models has enhanced the accuracy of semantic search capabilities but also amplified the computational demands for Approximate Nearest Neighbor Searches (ANNS). This complexity poses significant challenges in online and interactive services, where query latency is a critical performance metric. Traditional graph-based ANNS methods, while effective for managing large datasets, often experience substantial throughput reductions when scaled for intra-query parallelism to minimize latency. This reduction is largely due to inherent inefficiencies in the conventional fork-join parallelism model. To address this problem, we introduce AverSearch, a novel parallel graph-based ANNS framework that overcomes these limitations through a fully asynchronous architecture. Unlike existing frameworks that struggle with balancing latency and throughput, AverSearch utilizes a dynamic workload balancing mechanism that supports continuous, dependency-free processing. This approach not only minimizes latency by eliminating unnecessary synchronization and redundant vertex processing but also maintains high throughput levels. Our evaluations across various datasets, including both traditional benchmarks and modern large-scale model generated datasets, show that AverSearch consistently outperforms current state-of-the-art systems. It achieves up to 2.1-8.9 times higher throughput at comparable latency levels across different datasets and reduces minimum latency by 1.5 to 1.9 times.

Figures

Figures reproduced from arXiv: 2504.20461 by the authors.

Figure 1
Figure 1. The relationship between latency and throughput, expressed in queries per second (QPS), varies across different parallelism settings. We leverage all 48 available cores, orga￾nizing them into “𝑖𝑛𝑡𝑟𝑎×𝑖𝑛𝑡𝑒𝑟” groups, ranging from “1 × 48” to “24 × 2”. Here, “𝑖𝑛𝑡𝑟𝑎” represents the number of threads dedicated to each query, while “𝑖𝑛𝑡𝑒𝑟” indicates the number of independent concurrent queries. The analysis uses two well-k… view at source ↗
Figure 2
Figure 2. iQAN execution time distribution under different parallelism strategies with Wiki100M and recall at 0.9. Traditional approaches enhance search performance on graphs by optimizing their structures, whereas recent stud￾ies [50, 60] incorporate intra-query parallelism to reduce la￾tency. However, implementing such parallel strategies presents significant challenges. As an illustration, [PITH_FULL_IMAGE:figures/full_fi… view at source ↗
Figure 3
Figure 3. Edge-wise parallelism v.s. path-wise parallelism (§2.3.2) Algorithm 2 the Expand operation Input: the expanded candidate 𝑣, query 𝑞, priority queue 𝑄, graph 𝐺, distance function 𝛿 1: 𝑣.𝑠𝑡𝑎𝑡𝑒 ← 𝑐ℎ𝑒𝑐𝑘𝑒𝑑 2: 𝐵 ← ∅ 3: # edge-wise parallel knob 4: for all neighbor 𝑢 of 𝑣 in 𝐺 do 5: if 𝑢 is not visited then 6: mark 𝑢 as visited 7: 𝑢.𝑠𝑡𝑎𝑡𝑒 ← 𝑢𝑛𝑐ℎ𝑒𝑐𝑘𝑒𝑑 8: 𝑢.𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 ← 𝛿 (𝑢, 𝑞) 9: 𝐵 ← 𝐵 ∪𝑢 10: 𝑄 ← 𝑄.𝑚𝑒𝑟𝑔𝑒 (𝐵) whole Wikipedia … view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: iQAN CPU time breakdown for a single query with varying accuracy and parallelism strategies. “Serial time” for the joining phase; “Expand time” for useful expansions during the forking phase; “Redundant time” for unnecessary expansions; and “Sync time” resulting from t…
Figure 5
Figure 5. Figure 5: iQAN CPU time break￾down for a single query across vary￾ing 𝑤𝑖𝑑𝑡ℎ with 32 threads. 0 5 10 15 20 25 #Intra Threads 100 125 150 175 200 225 250 275 Memory Bandwidth (GB/s) 1x48 3x166x8 9x5 16x3 24x2 1x48 2x244x12 8x6 16x3 24x2 AVS iQAN [PITH_FULL_IMAGE:figures/full_fig_…
Figure 8
Figure 8. Figure 8: An illustration of two thread groups in AverSearch. Threads (represented by white boxes) interact with each other through shared data structures (represented by black boxes) asynchronously. (§4) devise an algorithm to approximate a slightly larger L￾threshold based on …
Figure 9
Figure 9. Figure 9: A timeline depicting the execution of a sub-queue maintainer thread and two distance calculator threads search￾ing in the example graph of Figure 3a. To further demonstrate our strategy, [PITH_FULL_IMAGE:figures/full_fig_p008_9.png]
Figure 10
Figure 10. Figure 10: QPS-latency curve under various accuracy targets in different embeddings. These figures demonstrate a trade-off between achieving low latency and high throughput, as both AverSearch and iQAN experience a decrease in throughput when increasing intra-query parallelism. …
Figure 11
Figure 11. Figure 11: Breakdown Analysis at “24x2”. 6 Related Work In this paper, we focus on enhancing intra-query parallelism for CPU-based graph ANNS indices. Besides the related works discussed in §2, the field has also seen various or￾thogonal advancements that complement our approach…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

72 extracted references · 45 canonical work pages

  1. [1]

    2012. Deep1B. https://disk.yandex.ru/d/11eDCm7Dsn9GA

    work page 2012

  2. [2]

    Ameer MS Abdelhadi, Christos-Savvas Bouganis, and George A Con- stantinides. 2019. Accelerated approximate nearest neighbors search through hierarchical product quantization. In 2019 International Conference on Field-Programmable Technology (ICFPT). IEEE, 90– 98

    work page 2019

  3. [3]

    Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. Advances in neural information processing systems 28 (2015)

    2015

  4. [4]

    Martin Aumueller, Erik Bernhardsson, and Alec Faitfull. 2023. ANN- Benchmarks. https://ann-benchmarks.com/index.html

    work page 2023

  5. [5]

    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

  6. [6]

    Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search

    2018

  7. [7]

    Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly- efficient billion-scale approximate nearest neighbor search. arXiv preprint arXiv:2111.08566 (2021)

    arXiv 2021

  8. [8]

    Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthijs Douze, Leon Bottou, Zhihao Jia, et al . 2024. MagicPIG: LSH Sampling for Efficient LLM Generation. arXiv preprint arXiv:2410.16179 (2024)

    arXiv 2024

Show all 72 references
  1. [9]

    Yuze Chi, Guohao Dai, Yu Wang, Guangyu Sun, Guoliang Li, and Huazhong Yang. 2016. Nxgraph: An efficient graph processing system on a single machine. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 409–420

    2016

  2. [10]

    cohere.ai. 2022. Cohere/wikipedia-22-12. https://huggingface.co/dat asets/Cohere/wikipedia-22-12

    2022

  3. [11]

    cohere.ai. 2022. Develop, test, and experiment with the industry’s first multilingual text understanding model that supports 100+ languages. https://cohere.com/blog/multilingual

    2022

  4. [12]

    cohere.ai. 2023. Cohere/wikipedia-2023-11-embed-multilingual-v3. https://huggingface.co/datasets/Cohere/wikipedia-2023-11-embed- multilingual-v3

    2023

  5. [13]

    Leonardo Dagum and Ramesh Menon. 1998. OpenMP: an industry standard API for shared-memory programming. IEEE computational science and engineering 5, 1 (1998), 46–55

    1998

  6. [14]

    Guohao Dai, Tianhao Huang, Yuze Chi, Ningyi Xu, Yu Wang, and Huazhong Yang. 2017. ForeGraph: Exploring large-scale graph processing on multi-FPGA architecture. In Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 217–226

    2017

  7. [15]

    Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG]

    2024 arXiv

  8. [16]

    facebookresearch. 2022. facebookresearch/faiss. https://github.com/f acebookresearch/faiss

    2022

  9. [17]

    Cong Fu and Deng Cai. 2016. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph.arXiv preprint arXiv:1609.07228 (2016). Efficient Graph-Based Approximate Nearest Neighbor Search Achieving: Low Latency Without Throughput Loss , ,

    2016 arXiv

  10. [18]

    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

  11. [19]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast approximate nearest neighbor search with the navigating spreading- out graph. arXiv preprint arXiv:1707.00143 (2017)

    2017 arXiv

  12. [20]

    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

  13. [21]

    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

  14. [22]

    Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, et al. 2022. Manu: a cloud native vector database management system. Proceedings of the VLDB Endowment 15, 12 (2022), 3548–3561

    2022

  15. [23]

    Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Twenty-Second International Joint Conference on Artificial Intelligence

    2011

  16. [24]

    Minyang Han and Khuzaima Daudjee. 2015. Giraph unchained: Barri- erless asynchronous parallel execution in pregel-like graph processing systems. Proceedings of the VLDB Endowment 8, 9 (2015), 950–961

    2015

  17. [25]

    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

  18. [26]

    Intel. 2024. Intel Memory Latency Checker v3.11. https://www.inte l.com/content/www/us/en/developer/articles/tool/intelr-memory- latency-checker.html

    2024

  19. [27]

    Junhyeok Jang, Hanjin Choi, Hanyeoreum Bae, Seungjun Lee, Miryeong Kwon, and Myoungsoo Jung. 2023. {CXL- ANNS}:{Software-Hardware} Collaborative Memory Disaggregation and Computation for{Billion-Scale} Approximate Nearest Neighbor Search. In 2023 USENIX Annual Technical Confer...

    2023

  20. [28]

    Yahoo Japan. 2024. Neighborhood Graph and Tree for Indexing High- dimensional Data. https://github.com/yahoojapan/NGT

    2024

  21. [29]

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in Neural Information Processing Systems 32 (2019)

    2019

  22. [30]

    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

  23. [31]

    Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg

  24. [32]

    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

  25. [33]

    Hervé Jégou Laurent Amsaleg. 2010. Datasets for approximate nearest neighbor search. http://corpus-texmex.irisa.fr/

    2010

  26. [34]

    Shengwen Liang, Ying Wang, Ziming Yuan, Cheng Liu, Huawei Li, and Xiaowei Li. 2022. VStore: in-storage graph based vector search accelerator. InProceedings of the 59th ACM/IEEE Design Automation Conference. 997–1002

    2022

  27. [35]

    Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chengruidong Zhang, Bailu Ding, Kai Zhang, et al

  28. [36]

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

    2020

  29. [37]

    Kejing Lu, Chuan Xiao, and Yoshiharu Ishikawa. 2024. Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search.arXiv preprint arXiv:2402.11354 (2024)

    2024 arXiv

  30. [38]

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61– 68

    2014

  31. [39]

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

    2018

  32. [40]

    Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhuli- pala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. Par- layANN: Scalable and Deterministic Parallel Graph-Based Approx- imate Nearest Neighbor Search Algorithms. In Proceedings of the 29th ACM SIGPLAN An...

    2024

  33. [41]

    Marius Muja and David G Lowe. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP (1) 2, 331-340 (2009), 2

    2009

  34. [42]

    Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. 2019. Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition 96 (2019), 106970

    2019

  35. [43]

    NeurIPS’2023. 2023. NeurIPS’23 Competition Track: Big-ANN. https: //big-ann-benchmarks.com/neurips23.html

    2023

  36. [44]

    Donald Nguyen, Andrew Lenharth, and Keshav Pingali. 2013. A lightweight infrastructure for graph analytics. In Proceedings of the twenty-fourth ACM symposium on operating systems principles. 456– 471

    2013

  37. [45]

    Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2023. Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus. arXiv preprint arXiv:2308.15136 (2023)

    2023 arXiv

  38. [46]

    OpenAI. 2023. OpenAI, all-MiniLM-L6-v2, GTE-small embeddings for Wikipedia Simple English. https://huggingface.co/datasets/Supaba se/wikipedia-en-embeddings

    2023

  39. [47]

    OpenAI. 2023. OpenAI embeddings for Wikipedia Simple English. https://www.kaggle.com/datasets/stephanst/wikipedia-simple- openai-embeddings

    2023

  40. [48]

    OpenAI. 2024. Introducing OpenAI o1. https://openai.com/o1/

    2024

  41. [49]

    OpenAI. 2024. New embedding models and API updates. https: //openai.com/blog/new-embedding-models-and-api-updates

    2024

  42. [50]

    Zhen Peng, Minjia Zhang, Kai Li, Ruoming Jin, and Bin Ren. 2023. iQAN: Fast and Accurate Vector Search with Efficient Intra-Query Par- allelism on Multi-Core Architectures. InProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programmin...

    2023

  43. [51]

    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

  44. [52]

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

    2008

  45. [53]

    Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish, Todd Mostak, Piotr Indyk, Samuel Madden, and Pradeep Dubey. 2013. Streaming similarity search over one billion tweets using parallel locality-sensitive hashing. Proceedings of the VLDB Endowment 6, 14 (2013), 1930–1941

    2013

  46. [54]

    , , Jingjia Luo, Mingxing Zhang, Kang Chen Xia Liao, Yingdi Shan, Jinlei Jiang, Yongwei Wu

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. , , Jingjia Luo, Mingxing Zhang, Kang Chen Xia Liao, Yingdi Shan, Jinlei Jiang, Yongwei Wu

  47. [55]

    Runhui Wang and Dong Deng. 2020. DeltaPQ: lossless product quan- tization code compression for high dimensional similarity search. Proceedings of the VLDB Endowment 13, 13 (2020), 3603–3616

    2020

  48. [56]

    Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. Analyticdb-v: A hybrid analytical engine towards query fusion for structured and unstructured data. Proceedings of the VLDB Endowment 13, 12 (2020), 3152–3165

    2020

  49. [57]

    Wikipedia. 2024. Wikipedia (simple English). https://simple.wikiped ia.org/wiki/Main_Page

    2024

  50. [58]

    WPJiang. 2024. HWTL_SDU-ANNS. https://github.com/WPJiang/H WTL_SDU-ANNS

    2024

  51. [59]

    Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N Holtmann-Rice, David Simcha, and Felix Yu. 2017. Mul- tiscale quantization for fast similarity search. Advances in neural information processing systems 30 (2017)

    2017

  52. [60]

    Ming Yang, Yuzheng Cai, and Weiguo Zheng. [n.d.]. CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search. In The Thirty-eighth Annual Conference on Neural Information Processing Systems

  53. [61]

    Mingyu Yang, Wentao Li, and Wei Wang. 2024. Fast High-dimensional Approximate Nearest Neighbor Search with Efficient Index Time and Space. arXiv preprint arXiv:2411.06158 (2024)

    2024

  54. [62]

    Rahul Yesantharao. 2022. Parallel Batch-Dynamic kd-trees. Ph.D. Dis- sertation. Massachusetts Institute of Technology

    2022

  55. [63]

    Yuanhang Yu, Dong Wen, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2022. GPU-accelerated Proximity Graph Approxi- mate Nearest Neighbor Search and Construction. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 552–564

    2022

  56. [64]

    Zhenrui Yue, Honglei Zhuang, Aijun Bai, Kai Hui, Rolf Jagerman, Hansi Zeng, Zhen Qin, Dong Wang, Xuanhui Wang, and Michael Ben- dersky. 2024. Inference Scaling for Long-Context Retrieval Augmented Generation. arXiv preprint arXiv:2410.04343 (2024)

    2024 arXiv

  57. [65]

    Hailin Zhang, Xiaodong Ji, Yilin Chen, Fangcheng Fu, Xupeng Miao, Xiaonan Nie, Weipeng Chen, and Bin Cui. 2024. Pqcache: Product quantization-based kvcache for long context llm inference. arXiv preprint arXiv:2407.12820 (2024)

    2024 arXiv

  58. [66]

    Jialiang Zhang, Soroosh Khoram, and Jing Li. 2018. Efficient large- scale approximate nearest neighbor search on OpenCL FPGA. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 4924–4932

    2018

  59. [67]

    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

  60. [68]

    Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou

  61. [2011]

    In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

    Searching in one billion vectors: re-rank with source coding. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 861–864

    2011

  62. [2021]

    In Proceedings of the 2021 International Conference on Management of Data

    Milvus: A Purpose-Built Vector Data Management System. In Proceedings of the 2021 International Conference on Management of Data. 2614–2627

    2021

  63. [2023]

    Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces.Proceedings of the VLDB Endowment 16, 8 (2023), 1979–1991

    2023

  64. [2024]

    arXiv preprint arXiv:2409.10516 (2024)

    Retrievalattention: Accelerating long-context llm inference via vector retrieval. arXiv preprint arXiv:2409.10516 (2024)

    2024 arXiv

Pith tools

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