Pith. sign in

REVIEW 2 major objections 4 minor 60 references

This paper claims that deleting a vector from a graph-based approximate nearest neighbor index can be made nearly as cheap as inserting one, while keeping recall stable or even improving it as deletions accumulate.

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-03 12:16 UTC pith:OZR2BGT6

load-bearing objection Clean combination of known techniques yields a plausible deletion path for graph ANNS; experiments are broad, but the connectivity proof doesn't cover the implemented pruning and recall-stability lacks a theoretical bound. the 2 major comments →

arxiv 2607.29173 v1 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 indexdynamic deletionin-place updateversioned edge invalidationMST repairstreaming vector searchretrieval-augmented generation
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.

The paper confronts the asymmetry in graph-based approximate nearest neighbor (ANNS) indexes: insertion is cheap because only outgoing neighbors are stored, but deletion requires repairing the unknown incoming edges that point to the removed vertex. MERIT's thesis is that you do not need to find or repair every incoming edge. Instead, you make the deleted vertex logically invisible immediately, repair only the 'readily searchable' boundary of its surviving neighbors plus a few recovered in-neighbors, and use a per-vertex version number to invalidate every stale incoming edge in O(1) without locating it. If deletions are indeed made invisible and the local repair preserves navigable routes, then dynamic workloads such as retrieval-augmented generation can remove stale or expired vectors at near-insertion cost without periodic rebuilds or recall collapse. The paper supports this with a complexity analysis and experiments showing up to 3.02x–18.87x faster deletion than prior state-of-the-art while maintaining stable recall.

Core claim

The central claim is that an in-place deletion can be decomposed into three ordered stages that together keep cost local and correctness global. First, the target vertex is marked invalid and its outgoing neighbors are snapshotted as repair seeds. Second, a bounded beam search recovers an approximate set of in-neighbors (vertices whose adjacency lists contain the deleted vertex); these are merged with the outgoing neighbors into a candidate set over which an incremental k_r-MST construction inserts up to k_r short edges per vertex, preserving connectivity and routing diversity under the graph's degree bound. Third, incrementing the target's version number logically invalidates every residual

What carries the argument

The pair of mechanisms that carries the argument is the k_r-MST local repair graph and the versioned-edge encoding. The repair graph is built over the union of the deleted vertex's outgoing neighbors and the in-neighbors recovered by a small beam search, using an incremental Prim-style construction that retains a mandatory MST backbone plus up to k_r−1 extra edges per vertex; this preserves connectivity and multiple routing choices after the vertex is removed. The versioned-edge scheme packs a 16-bit target version into each stored edge word (alongside a 48-bit vertex id) and increments the target's version on deletion, so a single O(1) version bump makes every incoming edge to the deleted v

Load-bearing premise

The bounded beam search (with a width proportional to the maximum out-degree) is assumed to find the in-neighbors that matter for routing; if it misses many important in-neighbors, version invalidation prevents wrong answers but leaves broken routes, and recall could decline as deletions accumulate.

What would settle it

Measure Recall@10 and search distance computations on a hub-heavy dataset (e.g., GloVe) after deleting 50% of vectors with MERIT, while logging the fraction of in-neighbors recovered by the bounded search per deletion. If recall drops by more than about two percentage points or search NDC rises while recovered in-neighbor count lags significantly behind actual in-degree for hub vertices, then the 'readily searchable' recovery assumption is violated and the guarantee fails.

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

If this is right

  • Deletion latency becomes independent of the deleted vertex's in-degree and of graph size; it is bounded by local repair parameters, bringing deletion cost in line with insertion cost.
  • Stale incoming edges no longer consume candidate-set capacity or expansion budget during beam search, because version mismatches filter them before they enter the queue.
  • Long-running sliding-window updates (delete plus insert) can maintain stable recall without periodic full rebuilds, since residual stale edges are progressively removed as adjacency lists are touched.
  • The approach applies to both hierarchical and single-layer graph indexes, suggesting it generalizes across graph ANN index families.
  • The finite 16-bit version counter is shown, under a uniform-reuse model, to support trillions of updates before wrap-around, so the mechanism is durable for long-running services.

Where Pith is reading between the lines

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

  • The approximate in-neighbor recovery suggests a testable dependency: on graphs with strong hubness, a fixed beam width may miss a large fraction of important in-neighbors; one could test whether an adaptive beam that grows with the deleted vertex's out-degree or recent query traffic improves recall stability.
  • Versioned invalidation could be extended beyond deletion to support concurrent updates and crash recovery, since it already detects version mismatches; the paper does not discuss this, but the encoding is a natural fit.
  • The repair strategy implicitly assumes that the 'readily searchable' in-neighbors are the ones that matter for routing; if a dataset's geometry makes important in-neighbors hard to reach from the entry point, the recall stability guarantee may degrade. A stress test on a dataset with irregular density could reveal this boundary.
  • The progressive cleanup means memory may still hold stale edge entries until their lists are rewritten; a reader might infer that memory footprint could grow under workloads that touch few lists, and that a trigger for forced compaction might be needed—this is not analyzed in the paper.

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

2 major / 4 minor

Summary. The paper proposes MERIT, an in-place deletion mechanism for graph-based approximate nearest neighbor indexes. Deletion proceeds in three stages: logical invalidation and snapshotting of the deleted vertex's outgoing neighbors; bounded-search recovery of approximate in-neighbors combined with a k_r-MST-style local repair; and versioned-edge invalidation that filters residual stale incoming edges. The authors instantiate MERIT on HNSW and Vamana and report that deletion latency is close to insertion latency, up to 3.02x–18.87x faster than Wolverine, FreshVamana, and IP-Vamana, while Recall@10 remains stable over 50 deletion batches or sliding-window update batches on several million-scale datasets and on Deep100M.

Significance. If the central claims hold, MERIT would be a practically useful step toward making graph-based ANNS indexes fully dynamic: deletion cost comparable to insertion, immediate visibility of deletions, and no periodic global cleanup. The paper is strong on the systems side: it integrates with two different graph families, reports extensive experiments across seven datasets including a 100M-scale run, provides an ablation isolating the MST-repair and versioning components, and gives a complexity analysis plus a probabilistic lifetime bound for the version counter. The main risk is not empirical breadth but whether the repair algorithm is guaranteed, or even measured, to preserve routing-relevant connectivity over sustained churn. I do not see circularity: the speedup claims are independent empirical comparisons, and hyperparameter choices are disclosed. The correctness of the recall-stability claim is what needs strengthening.

major comments (2)
  1. [§4.3, Definition 4.3, Algorithm 3] The connectivity guarantee for k_r-MST is proven only for RNG-based pruning of the complete graph K(C): the argument that every MST edge satisfies the RNG criterion is a statement about K(C). The implemented InsertAndPrune, however, prunes to degree bound M and operates on the full graph G, not on an isolated complete graph over C. A degree cap can evict an MST backbone edge, and existing edges outside C can also affect which edges survive pruning. Thus the proof as written does not establish that the repaired candidate set remains connected under the implemented procedure. Since the recall-stability claim depends on local connectivity after repair, this gap is load-bearing. Please either extend the proof to the actual InsertAndPrune operation or add an experimental check that tracks whether the MST backbone edges survive degree-bounded pruning.
  2. [§4.3, §6.3, §6.6] The statement that bounded search with e_f'_c = 2M recovers 'the readily searchable part of I(v_d) that affects near-term navigation' is an assumption, not a demonstrated invariant. Missed in-neighbors are version-invalidated, but their broken routes u -> v_d -> w are not repaired because u is not in candidate set C. The paper does not measure what fraction of routing-relevant in-neighbors is recovered, nor how misses accumulate over longer update streams. Experiments run for 50 batches, and the Deep100M experiment also uses a 50-batch horizon. Given that the headline includes 'keeps search recall stable or even improves it as deletions accumulate,' this needs either a formal bound on the effect of missed in-neighbors or an empirical study that varies e_f'_c and measures recovery coverage and recall decay well beyond 50 batches.
minor comments (4)
  1. [§6.3] The text contains a duplicated sentence: 'Answer to RQ2. Answer to RQ2.'
  2. [§6.3] The sentence 'Figure 9 reports the QPS and NDC' appears to refer to Figure 10, which is the figure whose caption describes QPS and NDC. Please fix the cross-reference.
  3. [§4.4] The versioned-edge encoding uses 16 bits for the version and 48 bits for the identifier. Please state explicitly what happens when a slot is reused exactly V_max times and the high bits wrap; the current text only gives a probabilistic lifetime bound under an idealized uniform-reuse model.
  4. [§5.1] In the complexity expression O(|E_C| log|C|) = O(|C|^2 log|C|), E_C is described as the edge set of the implicit complete graph over C. For readers not familiar with Prim's implementation, it may be clearer to write the Prim term as O(|C|^2 log|C|) directly.

Circularity Check

0 steps flagged

No circularity found: MERIT's claims rest on independent experiments and standard algorithmic arguments, not on definitions that presuppose their conclusions.

full rationale

The paper's central claims — deletion latency close to insertion and stable recall under accumulated deletions — are established by direct measurements against SOTA baselines on public datasets, not by a derived prediction that reduces to its inputs. The repair candidate set C is defined as the union of the outgoing-neighbor snapshot and search-recovered in-neighbors, but no equation predicts recall or latency from C by construction; the bounded-recovery step is explicitly labeled an intentional approximation whose adequacy is checked experimentally (§4.3: 'The recovery is intentionally approximate'). The k_r-MST connectivity argument is a standard exchange proof (MST edges satisfy the RNG criterion), and the complexity analysis is a conventional O(·) accounting with no fitted parameters masquerading as predictions. The single self-citation used for the search-cost bound ([48] in §4.3/§5.1) is not load-bearing: the claim that beam-search work grows with beam width is standard and independently cited. Hyperparameters (k_r, e_f'_c) are tuned on evaluation datasets, which is a methodological weakness but not circular reasoning. The concern that missed in-neighbors may break routes over long streams is a real correctness risk, not a circularity, because the paper does not derive its recall-stability claim from the recovery assumption; it demonstrates it empirically over a 50-batch horizon.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The central claim rests on empirical assumptions about routing-relevant recovery and on an idealized version-counter lifetime model. The formal connectivity guarantee has a gap between the proven RNG-pruning case and the implemented degree-bounded pruning. No new physical entities are introduced; the version table and deletion bitmap are data structures. Free parameters are k_r, e_f'_c, and the version width, with k_r tuned on evaluation datasets.

free parameters (3)
  • k_r (repair edges per candidate) = 2 (default; 1–5 ablated)
    Chosen by ablation on Sift1M and Gist1M (§6.5 RQ4-1) and used for all main results; controls the deletion-latency / recall tradeoff.
  • e_f'_c (repair beam width) = 2M (e.g., 64 or 128)
    Set by hand in §6.1 ('Unless otherwise stated, MERIT uses e_f'_c = 2M'); no ablation is reported, and it bounds recovery cost and candidate-set size.
  • version_bits = 16
    Engineering choice for a 64-bit edge word (§4.4); the probabilistic lifetime analysis in §5.2 is used to argue wrap-around is unlikely, but this width is still arbitrary.
axioms (4)
  • domain assumption Beam search from the deleted vector with beam width e_f'_c finds in-neighbors that are routing-relevant; unrecovered in-neighbors are not needed for navigation.
    Central design premise, stated in §3.2.1 and §4.3. If false, versioned invalidation filters stale edges but does not repair broken routes, so recall could degrade.
  • ad hoc to paper The k_r-MST local repair graph over C remains connected after the implemented degree-bounded pruning.
    The proof in §4.3 covers pure RNG pruning, but InsertAndPrune in Algorithm 3 also enforces degree bound M, which can evict MST backbone edges. No argument shows connectivity holds under the implemented pruning.
  • domain assumption The version counter does not wrap during the workload; the probabilistic bound in §5.2 assumes an idealized uniform slot-reuse model.
    The safe-budget calculation depends on every vertex slot being reused uniformly at random; real workloads with hot slots could wrap sooner. The paper acknowledges this is a model.
  • domain assumption The base graph (HNSW/Vamana) remains navigable when only the local boundary set C is repaired.
    MERIT does not assert a global navigability guarantee; the stable recall reported in experiments is the only evidence for this assumption.

pith-pipeline@v1.3.0-daily-deepseek · 21902 in / 13105 out tokens · 119955 ms · 2026-08-03T12:16:54.293014+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 ↗

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

    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. 13

    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 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