Pith. sign in

REVIEW 3 major objections 5 minor 60 references

Deleting a vector from a graph-based approximate nearest neighbor index can be made as cheap as inserting one: mark it invalid, recover a bounded subset of its in-neighbors, repair locally with a k_r-MST, and stamp every edge with the targe

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-04 03:15 UTC pith:OZR2BGT6

load-bearing objection MERIT is a serious dynamic-deletion system with a genuinely new repair/invalidation combination; the stable-recall headline is softer than the abstract claims, but it is worth refereeing. the 3 major comments →

arxiv 2607.29173 v2 pith:OZR2BGT6 submitted 2026-07-31 cs.DB

MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes

Zekai Wu , Jiabao Jin , Peng Cheng , Wangze Ni , Haoyang Li , Lei Chen , Junjie Yao , Jingkuan Song
show 1 more author
Heng Tao Shen
This is my paper
classification cs.DB
keywords approximate nearest neighbor searchgraph-based indexin-place deletiondynamic vector databaseversioned edge invalidationminimum spanning tree repairstreaming updatessearch recall
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper argues that efficient deletion in graph-based approximate nearest neighbor (ANNS) indexes does not require finding and repairing every edge that points to the deleted vector. Instead, it proposes MERIT, which combines three mechanisms: logical invalidation of the deleted vertex, a small bounded search to recover a useful subset of its in-neighbors, and a version-number stamp stored inside each edge so that any stale incoming edge is immediately filtered out no matter where it lives. If MERIT works as described, deletion in dynamic vector databases becomes nearly as cheap as insertion, search recall stays stable even after half the index is deleted, and the periodic full-graph rebuilds that current systems use to clean up deletions become unnecessary. The paper reports deletion latencies close to insertion latency and stable or improved recall on several real-world datasets.

Core claim

The central claim is that in-place deletion in graph-based ANNS can be both immediate and approximate-by-design, without sacrificing recall. MERIT marks the target vertex invalid, snapshots its outgoing neighbors, runs a beam search with the deleted vector's embedding as query to recover a subset of its in-neighbors, and then rebuilds a small local subgraph over the union of surviving out-neighbors and recovered in-neighbors using a k_r-MST repair. The load-bearing insight is the versioned edge word: each stored edge encodes the current version of its target vertex, so incrementing the deleted vertex's version instantly invalidates every residual stale incoming edge regardless of whether it

What carries the argument

The key mechanism is the versioned edge word: a 64-bit encoding where the high 16 bits store the target vertex's current version and the low 48 bits store its identifier. Deleting a vertex increments its version, which instantly makes every previously stamped edge to it invalid, even if that edge is never physically removed. Around this lives a three-stage repair: a bounded beam search (width e f'_c) proposes in-neighbor candidates, an adjacency-list test certifies which candidates really point to the deleted vertex, and a k_r-MST graph over the resulting candidate set inserts a minimum spanning tree plus up to k_r-1 extra short edges per vertex, all inserted bidirectionally and pruned to th

Load-bearing premise

The bounded search for in-neighbors runs on the graph after the deleted vertex has been marked invalid and therefore cannot expand through the deleted vertex; the method assumes this search still reaches enough of the affected in-neighborhood—especially for hub vertices whose in-neighbors were mostly reachable only through it—to let the k_r-MST repair preserve navigability.

What would settle it

Run a deletion workload on a graph where the target vertices are always high-degree hubs (e.g., the top 1% by in-degree), with uniform random deletion as control. If recall after 50% deletions drops significantly more under hub-focused deletion than under uniform deletion, the bounded recovery assumption is violated.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Deletion latency in graph-based ANNS becomes comparable to insertion latency, removing the asymmetry that forces lazy deletion or periodic rebuilds.
  • Search recall remains stable under high deletion rates (up to 50% of vectors) because residual stale edges are filtered by version mismatch rather than consuming search budget.
  • The same three-stage mechanism applies to both hierarchical multi-layer graphs and single-layer graphs, suggesting a generic recipe for dynamic graph indexes.
  • Versioned-edge invalidation eliminates the need for full-graph scans or explicit reverse-adjacency maintenance to locate affected in-neighbors.
  • Per-deletion cost is bounded by local parameters (beam width, repair degree, max out-degree) rather than global reverse-degree, so cost does not blow up for hub vertices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because the version counter is only 16 bits, slot reuse is capped by the counter's lifetime; the paper's probabilistic analysis assumes uniform slot reuse, so workloads that repeatedly reuse a small set of hot slots could exhaust version space much sooner and would need a wider counter or a compaction step.
  • The bounded recovery search cannot expand the deleted vertex itself, so a natural stress test is deleting only high-degree hub vertices in an adversarial order; the paper's stable-recall results use the given deletion schedules, not worst-case hub-focused churn.
  • The k_r-MST repair is agnostic to the graph's construction rule, so the same framework may extend to other directed proximity graphs where local connectivity matters, such as navigable small-world graphs.
  • Sensitivity to the recovery beam width e f'_c is worth testing explicitly: the paper fixes it at 2M, but lowering it further might degrade recall for hub-heavy workloads, while raising it would approach exact reverse-edge recovery and erode the deletion-latency advantage.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes MERIT, an in-place deletion mechanism for dynamic graph-based approximate nearest neighbor search. Deletion is decomposed into three stages: (i) logical invalidation of the deleted vertex and snapshotting of its outgoing neighbors (Algorithm 2), (ii) bounded-search recovery of approximate in-neighbors followed by k_r-MST local repair over the union of outgoing and recovered incoming neighbors (Algorithm 3), and (iii) versioned-edge invalidation that logically filters any residual stale edges without scanning the graph (§4.4). The authors give a complexity analysis of a single deletion, a probabilistic lifetime analysis of the 16-bit version counter, and extensive experiments on Sift1M, Gist1M, Deep1M/10M/100M, GloVe, and MSong, comparing against Wolverine, FreshVamana, and IP-Vamana. The central claims are that MERIT achieves deletion latency close to insertion latency, provides up to 3.02x–18.87x speedups over existing methods, and keeps search recall stable or even improves it as deletions accumulate.

Significance. If the claims hold, MERIT would be a practical contribution to dynamic graph-based ANNS, which is relevant to vector databases, RAG, and recommendation workloads. The paper has clear strengths: a clean decomposition of the deletion problem, explicit algorithmic components, an analytical cost model, a versioned encoding that avoids global reverse-edge cleanup, a component ablation studying the contribution of MST repair and versioned edges, and a 100M-scale experiment. The main risk is structural: the recovery of in-neighbors happens after the deleted vertex is invalidated, so in-neighbors reachable only through the deleted hub may be missed. The reported GloVe recall drop to 0.847 at 50% deletion and the reachability loss in Table 3 indicate that this concern is real and must be addressed before the stability claim can be accepted.

major comments (3)
  1. [§4.2–§4.3, Algorithms 2 and 3] The core stability claim depends on recovering enough of the in-neighborhood of the deleted vertex. In Algorithm 2, v_d is marked logically invalid (line 5) before MeritRepair is called (line 7). Algorithm 3 then runs KnnSearch for x_{v_d} with v_d invalid (line 1), so v_d can neither be expanded nor returned. Consequently, any in-neighbor u for which the only route from the entry point passes through v_d will not be in R and will not be added to the repair candidate set C. Versioned-edge invalidation (§4.4) filters the stale edge u→v_d but does not provide a replacement route; if u had no other path to the live graph, it becomes disconnected. The paper's own Table 3 shows vertex reachability dropping from 99.22% to 97.90% with k_r-MST after 50% deletion on Gist1M, and the RQ2 text reports GloVe Recall@10 falling to 0.8473 at 50% deletion. Both are consistent with this incomplete recover
  2. [§6.1 and §6.2] The related-work section mentions CleANN [54] as a recent dynamic graph-based ANNS approach with semi-lazy cleaning, but the experimental comparison (Figures 7–12, Table 3) includes only Wolverine, FreshVamana, and IP-Vamana. Since the abstract claims superiority over 'state-of-the-art (SOTA) methods', omitting a recently published dynamic baseline leaves the 3.02x–18.87x speedup and recall-stability claims incompletely supported. CleANN should be added to the experiments, or the authors should explicitly justify why it is not directly comparable in this evaluation context.
  3. [§4.3, Definition 4.3 and following paragraph] The connectivity guarantee of k_r-MST repair is asserted, not proven under the degree bound. The text argues that any MST of C is contained in the RNG, so RNG-based pruning preserves the MST backbone. However, InsertAndPrune also enforces the graph degree bound M. If a vertex's adjacency list is already saturated, inserting a bidirectional repair edge can evict existing edges — possibly including an MST edge just added. The manuscript does not specify InsertAndPrune's eviction policy or prove that the MST backbone survives degree-bounded pruning. Without such an invariant, the claim that 'the preserved backbone maintains reachability of the repaired candidate set' is not established. Define InsertAndPrune precisely and prove the backbone invariant, or state and verify experimentally that MST edges are never pruned under the used parameter settings.
minor comments (5)
  1. [§6.3 and §6.4] There are duplicated 'Answer to RQ2.' and 'Answer to RQ3.' phrases in the text; these should be cleaned up.
  2. [Table 3] 'Vertex Reachability' is not defined. Please state explicitly how it is measured (e.g., BFS from the entry point over the live graph) and why the 'before' value is not 100%.
  3. [§6.1] Each configuration is repeated three times and only the mean is reported. Adding standard deviations or min–max ranges would be valuable, especially because the stability claim is about variation across deletion batches.
  4. [§6.6] The Deep100M experiment says 'tuned initial recall' but does not explain what was tuned or how the initial recall was set. Please specify the parameter settings.
  5. [Algorithm 3, line 2] The adjacency test `v_d ∈ N(u)` is used to certify in-neighbors. Since edges carry target versions, clarify whether this test checks the raw stored identifier or the version-validated view of the adjacency list.

Circularity Check

0 steps flagged

No significant circularity; MERIT's claims are empirical and its self-citations are not load-bearing.

full rationale

MERIT's headline results are obtained by running the proposed algorithms against external baselines on standard public datasets under identical update sequences, with no parameter fitted to the reported recall or latency numbers. The complexity analysis in §5.1 is a direct accounting of the algorithm's bounded operations (O(M + ef'_c log n + |C|^2 log |C| + |C| k_r M)) rather than an inversion of empirical results, and the lifetime bound in §5.2 explicitly states its idealized uniform-reuse assumption and derives a Chernoff bound. The one self-citation, [48], appears alongside external references [35,47] for the standard beam-search complexity fact and is therefore not load-bearing. The skeptic's concern about in-neighbors reachable only through v_d is a genuine robustness limitation—reflected in the paper's own Table 3 reachability decline—but the paper explicitly states that recovery is approximate and delegates residual edges to versioned invalidation, so this is an empirical design limitation, not a circular derivation. No central claim reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 1 invented entities

The central claim rests on the standard RNG/MST inclusion theorem, on the empirical navigability assumption of graph search complexity, on the heuristic that a bounded post-invalidation search recovers routing-relevant in-neighbors, and on the idealized uniform-reuse model for version lifetime. These are domain assumptions, not fitted parameters.

free parameters (3)
  • k_r = 2 (default; 3 also viable)
    Repair degree: number of edges retained per candidate in k_r-MST; chosen by ablation (§6.5 RQ4-1), not derived; affects deletion latency vs recall trade-off.
  • e'_c = 2M
    Beam width for repair candidate discovery; set to 2 times max out-degree by hand (§6.1); bounds recovery cost and candidate set size.
  • version_bits = 16
    Width of version field in 64-bit edge word; chosen to balance address space and wrap-around lifetime; lifetime analysis assumes this width.
axioms (4)
  • standard math The MST of any candidate set C is contained in the Relative Neighborhood Graph (RNG) of C.
    Used in §4.3 to claim RNG pruning preserves the MST backbone and thus connectivity; standard result (Toussaint 1980).
  • domain assumption Graph beam search with beam width e'_c performs O(e'_c log n) distance computations on navigable proximity graphs.
    Used in §5.1 complexity analysis; assumes the graph has logarithmic-diameter navigation, which is the empirical basis of graph ANNS, not a proven property for all graphs.
  • ad hoc to paper The searchable in-neighbors recovered by a bounded search from x_{v_d}, after v_d is marked invalid, suffice to preserve routing.
    Central design heuristic (§4.3, Figure 6); if a deleted vertex was a hub connecting regions, the search (which cannot expand v_d) may miss in-neighbors and repair may fail; no worst-case guarantee offered.
  • domain assumption Version increments select vertex slots uniformly at random across deletions (idealized reuse model).
    Used for the probabilistic wrap-around bound in §5.2; explicitly stated as idealized; real workloads may exhibit hot slots.
invented entities (1)
  • Version-stamped edge word (16-bit target version + 48-bit ID) no independent evidence
    purpose: Invalidates stale incoming edges to a deleted vertex without locating them individually.
    A data-structure encoding, not an empirical entity; its effectiveness is only demonstrated in the paper's experiments, with no external falsifiable handle.

pith-pipeline@v1.3.0-alltime-deepseek · 22011 in / 13715 out tokens · 504427 ms · 2026-08-04T03:15:29.541628+00:00 · methodology

0 comments
read the original abstract

Graph-based indexes have become the dominant approach to approximate nearest neighbor search (ANNS) over high-dimensional data and play a crucial role in real-world applications such as retrieval-augmented generation, recommendation systems, and vector databases. Despite extensive progress in static graph construction and search, efficient in-place deletion remains challenging because obsolete vectors must be removed without allowing stale incoming edges to consume search capacity or expensive graph-wide maintenance to interrupt online services, e.g., retrieval-augmented generation (RAG) and recommendation platforms. To address this problem, we propose MERIT (MST-based Efficient Repair with In-place updaTes), an in-place update framework with three core techniques: (1) bounded search-based recovery that combines a deleted vertex's outgoing neighbors with its readily searchable in-neighbors, (2) $k_r$-Minimum Spanning Tree (MST) local repair that promotes local connectivity while retaining multiple routing choices for graph search, and (3) versioned-edge invalidation that immediately filters all stale incoming edges to the deleted vertex and progressively removes them as adjacency lists are rewritten. Its integration with the hierarchical HNSW index and the single-layer Vamana index demonstrates applicability across distinct graph structures. Extensive experiments on multiple real-world datasets show that MERIT processes deletion at nearly the cost of inserting one vector, achieves up to $3.02\times$--$18.87\times$ faster deletion than state-of-the-art (SOTA) methods, and keeps search recall stable or even improves it as deletions accumulate.

Figures

Figures reproduced from arXiv: 2607.29173 by Haoyang Li, Heng Tao Shen, Jiabao Jin, Jingkuan Song, Junjie Yao, Lei Chen, Peng Cheng, Wangze Ni, Zekai Wu.

Figure 1
Figure 1. Figure 1: Dynamic RAG workloads. RAG knowledge bases need to be refreshed as documents are cre￾ated, corrected, or removed; search and recommendation catalogs change continuously; user-specific memories are rewritten as users interact with the system; some privacy and compliance workflows require physically removing expired vectors [9, 52, 55]. These work￾loads call for a dynamic index that supports efficient insert… view at source ↗
Figure 2
Figure 2. Figure 2: Average insertion and deletion latency over update [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Distribution of original in-degree and recovered in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The three algorithmic components of Merit deletion: (1) logical invalidation and local repair seeding for the deleted vertex; (2) approximate construction of the affected repair candidate set and 𝑘-MST repair over the local candidate set; and (3) versioned-edge invalidation for residual reverse edges. identify vertices whose neighbor lists contain the deleted vertex 𝑣𝑑 , remove these stale incoming edges, … view at source ↗
Figure 6
Figure 6. Figure 6: A toy example of Merit local repair. (a) Search￾based recovery of repair candidates. (b) Incremental 𝑘𝑟-MST construction with 𝑘𝑟 = 2. (c) The repaired local topology. Although a MST guarantees connectivity, connectivity alone is insufficient for approximate nearest neighbor search (ANNS). Because each cut in an MST is crossed by only one edge, distant bridge edges, degree pruning, or subsequent edge deleti… view at source ↗
Figure 7
Figure 7. Figure 7: Amortized deletion time for Vamana-based methods. The gray dashed line marks the Vamana insertion time. [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: Post-deletion Recall@10 at deletion rates of 5% and 50%. [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Search throughput and average distance computations per query after each deletion batch at [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 12
Figure 12. Figure 12: Post-update Recall@10 under the fixed-cardinality sliding-window update workload. [PITH_FULL_IMAGE:figures/full_fig_p011_12.png] view at source ↗
Figure 15
Figure 15. Figure 15: Deep100M scalability over 50 deletion batches. [PITH_FULL_IMAGE:figures/full_fig_p012_15.png] view at source ↗
Figure 13
Figure 13. Figure 13: Merit 𝑘𝑟 sensitivity. Recall@10 Deletion latency v0 v1 v2 v3 Variant 0.99 Recall@10 0.01 0.02 0.03 (a) Sift1M. v0 v1 v2 v3 Variant 0.95 0.97 0.98 0.25 0.5 0.75 1 Deletion latency (ms/op) (b) Gist1M [PITH_FULL_IMAGE:figures/full_fig_p012_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Merit component ablation. RQ4-2. We isolate versioned edges and MST repair with four variants. Merit-v0 disables both and performs no repair; Merit￾v1 enables only versioned edges and likewise performs no repair; Merit-v2 enables only MST repair; and Merit-v3 enables both. As shown in [PITH_FULL_IMAGE:figures/full_fig_p012_14.png] view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 5 linked inside Pith

  1. [1]

    Cecilia Aguerrebere, Ishwar Bhati, Mark Hildebrand, Mariano Tepper, and Ted Willke. 2023. Similarity search in the blink of an eye with compressed indices. arXiv preprint arXiv:2304.04759(2023)

    Pith/arXiv arXiv 2023

  2. [2]

    Sunil Arya and David M Mount. 1993. Approximate nearest neighbor queries in fixed dimensions.. InSODA, Vol. 93. Citeseer, 271–280

    1993

  3. [3]

    Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. 2023. Retrieval-based language models and applications. InProceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 6: Tutorial Abstracts). 41–46. 12

    2023

  4. [4]

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

    2020

  5. [5]

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

    2014

  6. [6]

    Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2055–2063

    2016

  7. [7]

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

    1975

  8. [8]

    Ellis, Brian Whitman, and Paul Lamere

    Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere

  9. [9]

    Mingyue Cheng, Yucong Luo, Jie Ouyang, Qi Liu, Huijie Liu, Li Li, Shuo Yu, Bohou Zhang, Jiawei Cao, Jie Ma, Daoyu Wang, and Enhong Chen. 2025. A Survey on Knowledge-Oriented Retrieval-Augmented Generation.arXiv preprint arXiv:2503.10677(2025)

    Pith/arXiv arXiv 2025

  10. [10]

    Scott Cost and Steven Salzberg. 1993. A weighted nearest neighbor algorithm for learning with symbolic features.Machine learning10 (1993), 57–78

    1993

  11. [11]

    Abhinandan S Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. 2007. Google news personalization: scalable online collaborative filtering. InProceed- ings of the 16th international conference on World Wide Web. 271–280

    2007

  12. [12]

    Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. 2010. Understanding and Effectively Preventing the ABA Problem in Descriptor-Based Lock-Free Designs. In2010 13th IEEE International Symposium on Object/Component/Service- Oriented Real-Time Distributed Computing. 185–192. https://doi.org/10.1109/ ISORC.2010.10

    2010

  13. [13]

    Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun

    Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis. InProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP ’24). 270–285

    2024

  14. [14]

    Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. InProceedings of the 20th interna- tional conference on World wide web. 577–586

    2011

  15. [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.arXiv preprint arXiv:2401.08281(2024)

    Pith/arXiv arXiv 2024

  16. [16]

    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 Intelligence44, 8 (2021), 4139–4150

    2021

  17. [17]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph.Proceedings of the VLDB Endowment12, 5 (2017)

    2017

  18. [18]

    Hao Guo and Youyou Lu. 2025. Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. InProceedings of the 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’25). USENIX Association, 171–186

    2025

  19. [19]

    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 Endowment9, 1 (2015), 1–12

    2015

  20. [20]

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

    1998

  21. [21]

    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 Systems32 (2019)

    2019

  22. [22]

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

    2010

  23. [23]

    Donald B. Johnson. 1975. Priority queues with update and finding minimum spanning trees.Inform. Process. Lett.4, 3 (1975), 53–57. https://doi.org/10.1016/ 0020-0190(75)90001-0

    1975

  24. [24]

    Ruoxuan Li, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni, Lei Chen, Zhitao Shen, Wei Jia, Xiangyu Wang, Xuemin Lin, et al. 2025. SINDI: an Efficient Index for Approximate Maximum Inner Product Search on Sparse Vectors.arXiv preprint arXiv:2509.08395(2025)

    arXiv 2025

  25. [25]

    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 Engineering32, 8 (2019), 1475–1488

    2019

  26. [26]

    Dawei Liu, Bolong Zheng, Ziyang Yue, Fuhao Ruan, Xiaofang Zhou, and Chris- tian S Jensen. 2025. Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates.Proceedings of the VLDB Endowment18, 7 (2025), 2268–2280

    2025

  27. [27]

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

  28. [28]

    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 intelligence42, 4 (2018), 824–836

    2018

  29. [29]

    Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen. 2020. Pmd: An optimal transportation-based user distance for recommender systems. InAdvances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14–17, 2020, Proceedings, Part II 42. Springer, 272–280

    2020

  30. [30]

    Rajeev Motwani and Prabhakar Raghavan. 1996. Randomized algorithms.ACM Computing Surveys (CSUR)28, 1 (1996), 33–37

    1996

  31. [31]

    Marius Muja and David Lowe. 2009. Flann-fast library for approximate nearest neighbors user manual.Computer Science Department, University of British Columbia, Vancouver, BC, Canada5, 6 (2009), 12–29

    2009

  32. [32]

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

    2014

  33. [33]

    Emir Öztürk and Altan Mesut. 2024. Performance Analysis Of Chroma, Qdrant, And Faiss Databases.UNITECH–Sel. Pap(2024)

    2024

  34. [34]

    Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. The log-structured merge-tree (LSM-tree).Acta Informatica33 (1996), 351–385

    1996

  35. [35]

    Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data1, 1 (2023), 1–27

    2023

  36. [36]

    Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. InProceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532–1543

    2014

  37. [37]

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

    2020

  38. [38]

    William Pugh. 1990. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM33, 6 (1990), 668–676

    1990

  39. [39]

    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

  40. [40]

    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)

    Pith/arXiv arXiv 2021

  41. [41]

    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

  42. [42]

    Nenad Tomasev, Milos Radovanovic, Dunja Mladenic, and Mirjana Ivanovic

  43. [43]

    Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set.Pattern recognition12, 4 (1980), 261–268

    1980

  44. [44]

    Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li. 2012. Scalable k-nn graph construction for visual descriptors. In2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1106–1113

    2012

  45. [45]

    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. InProceedings of the 2021 International Conference on Management of Data. 2614–2627

    2021

  46. [46]

    Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu. 2020. A survey on large-scale machine learning.IEEE Transactions on Knowledge and Data Engineering34, 6 (2020), 2574–2594

    2020

  47. [47]

    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 Endowment14, 11 (2021), 1964–1978

    2021

  48. [48]

    Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, and Xuemin Lin. 2026. FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search.Proceedings of the ACM on Management of Data4, 1 (SIGMOD (2026), 1–27

    2026

  49. [49]

    Haike Xu, Magdalen Dobson Manohar, Philip A Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. 2025. In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search.arXiv preprint arXiv:2502.13826(2025)

    Pith/arXiv arXiv 2025

  50. [50]

    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. InProceedings of the 29th Symposium on Operating Systems Principles. 545–561

    2023

  51. [51]

    Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. 2025. Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search.Proceedings of 13 the VLDB Endowment18 (2025), 1825–1838

    2025

  52. [52]

    Xiao Yang, Kai Sun, Hao Xin, Yushi Sun, Nikita Bhalla, Xiangsen Chen, Sa- jal Choudhary, Rongze D Gui, Ziran W Jiang, Ziyu Jiang, et al . 2024. Crag- comprehensive rag benchmark.Advances in Neural Information Processing Sys- tems37 (2024), 10470–10490

    2024

  53. [53]

    Kun Yu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Lei Chen, Zhitao Shen, Jingkuan Song, Hengtao Shen, and Xuemin Lin. 2025. Approximate Nearest Neigh- bor Search of Large Scale Vectors on Distributed Storage.arXiv preprint arXiv:2510.17326(2025)

    arXiv 2025

  54. [54]

    Ziyu Zhang, Yuanhao Wei, Joshua Engels, and Julian Shun. 2026. CleanANN: Effi- cient and Robust Full Dynamism in Graph-based Approximate Nearest Neighbor Search. InProceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26). 247–260. https://doi.org/10.1145/3816782.3819219

    arXiv 2026

  55. [55]

    Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, Jie Jiang, and Bin Cui. 2026. Retrieval- augmented generation for ai-generated content: A survey.Data Science and Engineering(2026), 1–29

    2026

  56. [56]

    Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, Xuemin Lin, Heng Tao Shen, Jingkuan Song, and Peng Cheng. 2025. VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search.Proc. VLDB Endow.18, 12 (Aug. 2025), 5017–5030

    2025

  57. [57]

    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. In2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 330–333. 14

    2019

  58. [2011]

    InProceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011)

    The Million Song Dataset. InProceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011)

    2011

  59. [2013]

    The role of hubness in clustering high-dimensional data.IEEE transactions on knowledge and data engineering26, 3 (2013), 739–751

    2013

  60. [2014]

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

    2014