Pith. sign in

REVIEW 3 major objections 5 minor 70 references

Yi shows that graph-based ANN indexes on disk can be updated in place — 1.75x faster update throughput and 1.8x faster concurrent search than prior systems on 800M vectors, with 73% of the peak memory.

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-01 22:52 UTC pith:CJ7MIU7I

load-bearing objection Real new mechanism and credible 800M results, but the deletion-repair guarantee is an unproven heuristic; deserves serious review with artifacts or analysis. the 3 major comments →

arxiv 2607.15576 v1 pith:CJ7MIU7I submitted 2026-07-17 cs.DB cs.IR

Efficient and Effective In-place Graph-based Vector Index Updates

Haotian Liu , Yujun He , Bo Tang This is my paper
classification cs.DB cs.IR
keywords graph-based vector indexapproximate nearest neighbor searchin-place index updatevector-level update mechanismLRU delete listbillion-scale indextasklet schedulingvector file system
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 seeks to show that graph-based approximate-nearest-neighbor (ANN) indexes on disk can be updated in place — inserting and deleting vectors individually, without periodic offline merges — while keeping both update throughput and search recall high. Its central move is a 'vector-level' update mechanism that decomposes each insert or delete query into fine-grained per-vector tasks, so that the expand-and-prune work shared by insert and delete is executed once per affected vector instead of once per query. On top of this, the paper's Yi system layers a tasklet-based execution engine that suspends on I/O and conflicts, an asynchronous buffer manager that keeps hot pages resident, and a vector file system that separates the navigation graph from raw vector data. The paper reports 1.75x higher update throughput and 1.8x higher concurrent search throughput than the prior best graph-based system on an 800M-vector dataset, using 73% of its peak memory and fewer cores. If right, this removes the batch-tuning and merge-sprawl costs that make current streaming billion-scale vector search difficult.

Core claim

The load-bearing discovery is that the connection-establishment procedures of insert and delete share the same two steps — expand a given vector's outgoing neighbor list by the new/deleted vector and its neighbors, then prune to the maximum out-degree — so they can be unified into a single 'connect task' per affected vector. Yi keeps deleted vectors in a fixed-size LRU delete list rather than removing them immediately, and populates a connect list from the search results of inserted vectors (plus random sampling when inserts are rare); each connect task then repairs one vector's neighbor list for all pending updates at once. The paper argues that this consolidation eliminates the redundant v

What carries the argument

The central mechanism is the vector-level connect task: it merges the expand-and-prune logic of insert and delete into one operation per vector, so each affected vector's outgoing neighbor list is repaired once regardless of how many updates touch it. This is supported by the LRU delete list, which keeps deleted vectors accessible long enough for in-neighbors to be visited, and a connect list fed by insert searches and, in delete-only workloads, random sampling. Around this, the tasklet-based execution engine (C++20 coroutines that suspend on page I/O and conflicts), the asynchronous buffer manager (ref-counted buffers with copy-on-write commit), and the vector file system (separate navigati

Load-bearing premise

The premise that a deleted vector kept in the fixed-size LRU list will stay accessible long enough for all its in-neighbors to be visited is asserted as 'almost certain' without a formal guarantee; if the LRU is too small or visit patterns miss some in-neighbors, recall degrades after deletions (the paper's own data shows 2% LRU underperforms a full scan).

What would settle it

Run a deletion-only workload on an index with highly skewed in-degrees and measure recall as LRU size varies: if recall falls below full-scan recall for any LRU size that still achieves the claimed throughput, the central heuristic fails. More directly, instrument Yi to count, for each evicted deleted vector, the fraction of its original in-neighbors that actually visited it while it was in the LRU; if that fraction is not close to 1 for realistic workloads, the 'almost certain' rationale is empirically false.

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

If this is right

  • If the claims hold, streaming insert and delete can run continuously at billion scale without the offline merge phase that dominates update cost in existing systems.
  • Update throughput no longer depends on a user-tuned batch size; the system applies each update immediately and instead depends on the fixed LRU delete-list size.
  • Memory usage becomes bounded by the fixed 4GB buffer plus the LRU delete list, eliminating the memory spikes of merge operations.
  • Search throughput during updates becomes stable rather than oscillating between online and offline phases, because CPU and I/O are not periodically consumed by merges.
  • Deletion-only workloads can maintain recall comparable to a full-scan approach, provided the LRU delete list is large enough (4% of the index in the paper's tests).

Where Pith is reading between the lines

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

  • The 'almost certain' assumption about LRU retention could be replaced by a probabilistic guarantee if in-neighbor visit rates were modeled; the paper gives no bound, only an experiment showing 4% LRU matches full-scan recall on 1M vectors.
  • The principle of deferring and consolidating repair work per vector may generalize beyond ANN graphs to other singly-linked dynamic structures where deletions require knowing incoming edges.
  • A testable extension: measure recall under delete-only workloads on datasets with skewed in-degree distributions; if the LRU size must grow with maximum in-degree rather than with the number of vectors, the fixed-percentage sizing rule will fail.
  • The layout insight — that update phases can run on compressed navigation data while search needs raw vectors — suggests an optimized storage tiering where raw vectors are kept on slower media without hurting update throughput.

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 Yi, a disk-resident graph-based ANN index update system that supports in-place insertions and deletions. The core idea is a vector-level update mechanism that unifies the expand/prune steps of insert and delete into fine-grained connect tasks. This is implemented through three components: a tasklet-based execution engine (C++20 coroutines), an asynchronous buffer manager with suspend-on-conflict page access, and a vector file system that separates graph topology from raw vector data. The central empirical claim is that Yi sustains stable, high update throughput and search throughput while preserving recall on 100M and 800M datasets, outperforming OdinANN, DiskANN, and SPFresh with lower memory and fewer CPU threads. The paper also includes component-wise breakdown and targeted scenarios (100% replacement, deletion-only, spatial locality).

Significance. If the claims hold, the contribution is substantial: Yi would be the first practical system to combine in-place insert and delete on billion-scale disk-resident graph ANN indexes with stable throughput and recall. The decomposition insight is elegant, and the 100M/800M comparisons show large, consistent throughput and memory advantages over strong baselines. The strengths are the detailed system description and the broad evaluation. However, the 'good search result quality' half of the central claim rests on a delete-repair heuristic that is not formally analyzed and is only partially evaluated: the paper provides no billion-scale delete-only or deletion-heavy recall experiments, no formal bound for the LRU delete-list guarantee, and no code/artifact release or repeated runs with error bars. These gaps are load-bearing because the headline claim is empirical and because delete repair directly affects recall.

major comments (3)
  1. [Section 3 and Section 5.3] The delete-repair guarantee is not established. The rationale in Section 3 states that keeping a deleted vector in the fixed-size LRU 'almost certain[ly]' causes all its in-neighbors to be visited, but no bound or adversarial analysis is given. In deletion-only workloads the connect list is filled by randomly sampling on-disk vectors; with out-degree R=96 and N=1M, a random sample of size R contains roughly R^2/N ~ 0.009 in-neighbors of a given deleted vector under a uniform model. Consequently most in-neighbor repairs may never happen before eviction, and an evicted vector's disk slot can be reused, leaving stale references in unrepaired neighbor lists. The paper's own Figure 15 shows LRU-2% below FullScan and LRU-4% only comparable at 1M scale; no billion-scale delete-only recall result is reported. Since recall under deletions is half of the central claim, this needs either a quantita
  2. [Section 5.1] The main performance claims are empirical and are presented as single curves without error bars or multiple runs. The paper also does not state any code or data artifact availability. The IP-DiskANN baseline in Section 5.3 is re-implemented by the authors using Yi's components, which can bias the comparison. Because the headline claims ('1.75x update throughput', '1.8x concurrent search throughput', 'comparable recall') are entirely empirical, the paper should provide the artifact, report variance over repeated runs, and clarify the exact IP-DiskANN configuration and implementation status.
  3. [Section 4.3] The concurrency-control protocol is described operationally, but its correctness is only asserted: 'Based on the above mechanisms, we resolve all pairwise conflicts in Table 2.' No invariant-based argument or exhaustive interleaving analysis is given for the COW/update_ready protocol, and no stress test with adversarial read/write interleavings is reported. Since the system permits concurrent search, updates, and asynchronous writeback, a lost update or a stale read could silently corrupt search results. A formal or at least systematic argument for the protocol's correctness is needed to support the claim that Yi is a dependable in-place update system.
minor comments (5)
  1. [Abstract and Introduction] The throughput numbers are inconsistent across the abstract ('1.8x'), the introduction ('1.76x'), and Figure 1's caption ('1.81x'). Please harmonize these values.
  2. [Figure 11 caption] The caption contains repeated '(a) Update Throughput(a) Update Throughput...' text; this appears to be a formatting artifact and should be fixed.
  3. [Section 5.1] The naming convention defines DEEP100M but not DEEP1M/SIFT1M; please define the 1M-scale variants used in Section 5.3.
  4. [Figure 10] The sub-figure labels seem inconsistently ordered ('(a) Schema block' vs 'PQ Block'); please align the labels with the referenced block types.
  5. [Section 5.3] When describing the IP-DiskANN comparison, clarify whether IP-DiskANN is the official implementation or a re-implementation from the paper, and list which parameters were used for its search-based in-neighbor identification.

Circularity Check

0 steps flagged

No significant circularity: central throughput/recall claims are empirical; the only self-citation (Tao tasklets) is not load-bearing.

full rationale

This is an empirical systems paper. The headline results (1.75x update throughput, 1.8x concurrent search throughput, 73% peak memory) are measured against external baselines on DEEP100M and SIFT800M; no headline quantity is derived algebraically from an input assumption. The vector-level update mechanism is an engineering consolidation of the shared Expand/Prune steps of Insert and Delete, and its benefit is validated by the paper's own ablation (+Tasklet 4.02x, +Buffer 1.33x, +Layout 1.04x) and by recall comparisons against full-scan merges. The delete-repair guarantee is explicitly heuristic: Section 3 says keeping a deleted vector in the LRU 'makes it almost certain that all of its in-neighbors will eventually be visited,' and Figure 15 shows LRU-2% below FullScan under delete-only workloads. That is an unproven correctness assumption and a genuine threat to the 'good search result quality' claim under delete-heavy workloads, but it is not circular: recall is not defined in terms of the LRU size, and the 4% setting is an empirical choice, not a fitted predictor. The only overlapping self-citation is [39] (Tao), used for the tasklet naming and the 'decomposition simplifies scheduling' principle; it is not load-bearing because the tasklet engine's benefit is demonstrated by the paper's own breakdown, and no uniqueness theorem or forced ansatz is imported from the authors' prior work. I find no step where a prediction reduces by construction to its inputs.

Axiom & Free-Parameter Ledger

4 free parameters · 4 axioms · 0 invented entities

The paper introduces engineering artifacts (tasklets, buffer manager, vector file system) but no new physical or mathematical entity. The assumptions above are the main unproved ingredients.

free parameters (4)
  • delete-list LRU size = 4% of initial index size (2% variant tested)
    Section 5.2 fixes 4%; Section 5.3 deletion-only experiments show LRU-2% recalls below full-scan and LRU-4% matches it (Figure 15). This hand-picked size is load-bearing for the 'good search quality' claim.
  • in-memory buffer pool size = 4GB
    Fixed budget for the asynchronous buffer manager (Section 5.2); no sensitivity study, but peak memory and throughput are direct functions of it.
  • maximum out-degree R = 96
    Set to match OdinANN's configuration (Section 5.2). It governs graph quality and update cost and is not derived.
  • random connect-list sampling size = equal to graph out-degree in experiments
    Section 3 and Section 5.3: delete-only workloads trigger connect tasks by randomly sampling vectors; the sample size determines whether repairs reach affected in-neighbors and is not derived.
axioms (4)
  • domain assumption A bounded-degree proximity graph with beam search produces acceptable approximate NN search quality.
    Inherited from DiskANN/HNSW; Yi's quality is measured relative to this standard (Section 2.1).
  • ad hoc to paper Retaining deleted vectors in the LRU cache long enough exposes almost all in-neighbors.
    Section 3: 'almost certain that all of its in-neighbors will eventually be visited.' No bound or proof; central to deletion quality.
  • domain assumption Raw vector data is not needed during updates, only compressed PQ data and graph topology.
    Observed in Figure 3 for the tested datasets (Section 2.3 Issue 4); assumed general across workloads.
  • ad hoc to paper The asynchronous buffer manager's suspend-on-conflict protocol resolves all page access conflicts without deadlock or starvation, and preserves search/update correctness.
    Section 4.3.2 claims Table 2's conflicts are all handled by the protocol; no formal correctness proof is provided.

pith-pipeline@v1.3.0-alltime-deepseek · 20913 in / 14938 out tokens · 148192 ms · 2026-08-01T22:52:34.165452+00:00 · methodology

0 comments
read the original abstract

In the era of Large Language Models (LLMs), efficient vector updates are critical for capturing real-time information from rapidly evolving data. However, it is not trivial to process frequent vector insert and delete updates and maintain a high recall of the search results simultaneously. Specifically, the cluster-based vector indexing methods have high update throughput but low search result quality. Existing out-of-place graph-based vector indexing update approaches suffer from poor update throughput due to the need to periodically merge update batches into the underlying graph index. Building a vector data system that supports efficient and effective in-place updates is inherently challenging. In this work, we propose Yi to achieve it. In particular, Yi supports in-place graph-based vector indexing updates with consistently high update throughput and good search result quality. The key idea of Yi is decomposition facilitates consolidation. In particular, we introduce a vector-level update mechanism and architect Yi with three core components: (i) a tasklet-based execution engine, (ii) an asynchronous buffer manager, and (iii) a vector file system. Experimental results demonstrate that Yi achieves 1.75x higher update throughput and 1.8x higher concurrent search throughput than the state-of-the-art systems on the 800M dataset, while using only 73% of the peak memory and fewer CPU cores.

Figures

Figures reproduced from arXiv: 2607.15576 by Bo Tang, Haotian Liu, Yujun He.

Figure 1
Figure 1. Figure 1: Elapsed time to replace 1M data in a 100M index. All systems [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Inserting and Deleting 20M vectors in OdinANN with dif [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Effect of raw data on build and search vector. This motivates us to devise an efficient data layout to im￾prove block access efficiency for different subroutines. 3 CORE IDEA: VECTOR-LEVEL UPDATE MECHANISM Logically, the straightforward in-place update solution in Section 2.3 utilizes a query-level update mechanism as it processes each in￾sert or delete query individually. Based on the above discussion, di… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the vector-level update mechanism [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: System architecture of Yi tasklets as the basic execution units and build a tasklet-based execution engine for them. • Asynchronous Buffer Manager (Section 4.3). To address the ineffective cache schemes in existing graph-based systems (Issue 3), we design an asynchronous buffer manager that caches vectors and pages across update operations. It abstracts page access protocols for vector updates and handles … view at source ↗
Figure 6
Figure 6. Figure 6: Tasklet generation in Yi conflict-free), it is pushed back into the tasklet queue, where CPUs can pick it up and resume its execution (see [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Page access protocol in Yi 18 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Bitmap blocks Schema blocks 2 25 26 27 28 Flexible blocks free mem_v: 0 disk_v: 0 17 mem_v: 3 disk_v: 3 16 mem_v: 2 disk_v: 2 20 mem_v: 6 disk_v: 4 15 mem_v: 8 disk_v: 5 21 mem_v: 4 disk_v: 2 16 mem_v: 2 disk_v: 1 Free list Dirty list 5 mem_v: 1 disk_v: 1 Buffer Map allocate a free buffer for the block 14 mem_v: 1 di… view at source ↗
Figure 9
Figure 9. Figure 9: Concurrency control of a specific buffer [PITH_FULL_IMAGE:figures/full_fig_p007_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Illustration of vector file system to suspend (e.g., 𝑅 (1) 4 and 𝑅 (1) 5 ). Once the last active reader (i.e., 𝑅 (1) 3 ) finishes, it applies the update on the original page content. After such modification, other tasklets are resumed (i.e., 𝑅 (2) 4 , 𝑅 (2) 5 , and 𝑊 (2) 2 ). This mechanism avoids the 2 - 3 conflict by suspending all other tasklets during the update of the original page. get_free(). When … view at source ↗
Figure 11
Figure 11. Figure 11: Overall performance in DEEP100M dataset, inserting and deleting 30M vectors from an index of 100M. [PITH_FULL_IMAGE:figures/full_fig_p010_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Overall performance in SIFT800M dataset, inserting and deleting 40M vectors from an index of 800M. [PITH_FULL_IMAGE:figures/full_fig_p011_12.png] view at source ↗
Figure 16
Figure 16. Figure 16: Recall comparison between Yi and a full-scan-based merge method under update scenarios with spatial locality. As shown in [PITH_FULL_IMAGE:figures/full_fig_p011_16.png] view at source ↗
Figure 14
Figure 14. Figure 14: Recall of Yi and full scan merge for 100% replacement. LRU-2% LRU-4% FullScan 0 10 20 30 40 50 Round 0.80 0.85 0.90 0.95 1.00 Recall10@10 (a) DEEP1M 0 10 20 30 40 50 Round 0.80 0.85 0.90 0.95 1.00 Recall10@10 (b) SIFT1M [PITH_FULL_IMAGE:figures/full_fig_p011_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Recall of Yi and full scan merge for 50% delete only. of DEEP10M, then replace 5M vectors from it for each method with 12 cores. Figures 13(a) and 13(b) show the update through￾put and recall of both methods under the same search parameter during updates. As shown in the figures, our update mechanism achieves recall comparable to that of IP-DiskANN while delivering 3× higher update throughput. This improv… view at source ↗
Figure 17
Figure 17. Figure 17: Breakdown Analysis. denoted as 𝑐1, . . . , 𝑐16. These clusters vary in both size and spatial distribution. We initialize the index using the vectors from first eight clusters, i.e., 𝑐1, 𝑐2, . . . , 𝑐8. Then, in round 𝑖 (𝑖 ≤ 8), we delete vectors from cluster 𝑐𝑖 and insert vectors from cluster 𝑐𝑖+8, thereby maintaining a constant number of eight active clusters throughout the experiment. After each round, … 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

70 extracted references · 1 canonical work pages

  1. [1]

    http://corpus-texmex

    2011.Datasets for approximate nearest neighbor search. http://corpus-texmex. irisa.fr/

    2011

  2. [2]

    https://www.openstd.org/jtc1/sc22/wg21/docs/papers/2017/n4649.pdf

    2017.Working Draft, Technical Specification for C++ Extensions for Coroutines. https://www.openstd.org/jtc1/sc22/wg21/docs/papers/2017/n4649.pdf

    2017

  3. [3]

    https://big-ann-benchmarks.com/ neurips21.html

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

    2021

  4. [4]

    https://github.com/intellistream/IP-DiskANN

    2025.IP-DiskANN. https://github.com/intellistream/IP-DiskANN

    2025

  5. [5]

    https://github.com/pgvector/pgvector

    2025.pgvector. https://github.com/pgvector/pgvector

    2025

  6. [6]

    https://github.com/SPFresh/SPFresh

    2025.SPFresh. https://github.com/SPFresh/SPFresh

    2025

  7. [7]

    Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. 1998. An optimal algorithm for approximate nearest neighbor searching fixed dimensions.JACM45, 6 (1998), 891–923

    1998

  8. [8]

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

    2020

  9. [9]

    Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art.SIGMOD3, 1 (2025), 1–31

    2025

  10. [10]

    Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index.TPAMI 37, 6 (2014), 1247–1260

    2014

  11. [11]

    Artem Babenko and Victor Lempitsky. 2017. Product split trees. InCVPR. 6214– 6222

    2017

  12. [12]

    Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting the inverted indices for billion-scale approximate nearest neighbors. InECCV. 202– 216

    2018

  13. [13]

    Jeffrey S Beis and David G Lowe. 1997. Shape indexing using approximate nearest- neighbour search in high-dimensional spaces. InCVPR. IEEE, 1000–1006

    1997

  14. [14]

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

    1975

  15. [15]

    Cheng Chen, Chenzhe Jin, Yunan Zhang, Sasha Podolsky, Chun Wu, Szu- Po Wang, Eric Hanson, Zhou Sun, Robert Walzer, and Jianguo Wang. 2024. SingleStore-V: An Integrated Vector Database System in SingleStore.PVLDB17, 12 (2024), 3772–3785

    2024

  16. [16]

    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 12 fast approximate nearest neighbor search. https://github.com/Microsoft/SPTAG

    2018

  17. [17]

    Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. InSTOC. 537–546

    2008

  18. [18]

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality- sensitive hashing scheme based on p-stable distributions. InSCG. 253–262

    2004

  19. [19]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2020. Aspen: A Framework for Dynamic Graphs. InProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. 576–589

    2020

  20. [20]

    Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. InWWW. 577–586

    2011

  21. [21]

    Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. 1977. An algo- rithm for finding best matches in logarithmic expected time.TOMS3, 3 (1977), 209–226

    1977

  22. [22]

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

    2019

  23. [23]

    Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search.SIGMOD3, 1 (2025), 1–26

    2025

  24. [24]

    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 Conference on Operating Systems Design and Implementation(Boston, MA, USA)(OSDI ’25). USENIX Association, USA, Article 10, 16 pages

    2025

  25. [25]

    Hao Guo and Youyou Lu. 2025. OdinANN: Direct Insert for Consistently Stable Performance in Billion-Scale Graph-Based Vector Search. InFAST. https:// storage.cs.tsinghua.edu.cn/papers/fast26-odinann.pdf

    2025

  26. [26]

    Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In AAAI

    2011

  27. [27]

    Junfeng He, Wei Liu, and Shih-Fu Chang. 2010. Scalable similarity search with optimized kernel hashing. InSIGKDD. 1129–1138

    2010

  28. [28]

    Yongjun He, Jiacheng Lu, and Tianzheng Wang. 2020. CoroBase: coroutine- oriented main-memory database engine.PVLDB14, 3 (2020), 431–444

    2020

  29. [29]

    Masajiro Iwasaki. 2016. Pruned bi-directed k-nearest neighbor graph for prox- imity search. InSISAP. Springer, 20–33

    2016

  30. [30]

    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.NIPS32 (2019)

    2019

  31. [31]

    Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in one billion vectors: re-rank with source coding. InICASSP. IEEE, 861–864

    2011

  32. [32]

    killer nanoseconds

    Christopher Jonathan, Umar Farooq Minhas, James Hunter, Justin Levandoski, and Gor Nishanov. 2018. Exploiting coroutines to attack the" killer nanoseconds". PVLDB11, 11 (2018), 1702–1714

    2018

  33. [33]

    Zuhair Khayyat, Karim Awara, Amani Alonazi, Hani Jamjoom, Dan Williams, and Panos Kalnis. 2017. GraphOne: A Data Store for Real-Time Analytics on Evolving Graphs.FAST17 (2017), 249–263

    2017

  34. [34]

    1975.Queueing Systems, Volume 1: Theory

    Leonard Kleinrock. 1975.Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York. The classic, foundational text on queueing theory

    1975

  35. [35]

    Brian Kulis and Kristen Grauman. 2009. Kernelized locality-sensitive hashing for scalable image search. InICCV. IEEE, 2130–2137

    2009

  36. [36]

    Viktor Leis, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2014. Morsel- driven parallelism: a NUMA-aware query evaluation framework for the many- core age. InSIGMOD. 743–754

    2014

  37. [37]

    Sen Li, Fuyu Lv, Taiwei Jin, Guli Lin, Keping Yang, Xiaoyi Zeng, Xiao-Ming Wu, and Qianli Ma. 2021. Embedding-based product retrieval in taobao search. In SIGKDD. 3181–3189

    2021

  38. [38]

    Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chengruidong Zhang, Bailu Ding, Kai Zhang, Chen Chen, Fan Yang, Yuqing Yang, and Lili Qiu. 2024. RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval. InarXiv

    2024

  39. [39]

    Haotian Liu, Runzhong Li, Ziyang Zhang, and Bo Tang. 2024. Tao: Improv- ing Resource Utilization while Guaranteeing SLO in Multi-tenant Relational Database-as-a-Service.SIGMOD2, 4, Article 205 (Sept. 2024), 26 pages. https: //doi.org/10.1145/3677141

    work page doi:10.1145/3677141 2024

  40. [40]

    Marathe, Daniel W

    Peter Macko, Virendra J. Marathe, Daniel W. Margo, and Margo I. Seltzer. 2015. LLAMA: Efficient Graph Analytics Using Large Multiversioned Arrays. In2015 IEEE 31st International Conference on Data Engineering (ICDE). IEEE, 363–374

    2015

  41. [41]

    Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.TPAMI 42, 4 (2018), 824–836

    2018

  42. [42]

    Andrew W Moore. 2000. The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data. InUAI. 397–405

    2000

  43. [43]

    Yadong Mu and Shuicheng Yan. 2010. Non-metric locality-sensitive hashing. In AAAI, Vol. 24. 539–544

    2010

  44. [44]

    Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data.TPAMI36, 11 (2014), 2227–2240

    2014

  45. [45]

    David Nister and Henrik Stewenius. 2006. Scalable recognition with a vocabulary tree. InCVPR, Vol. 2. Ieee, 2161–2168

    2006

  46. [46]

    Maxim Raginsky and Svetlana Lazebnik. 2009. Locality-sensitive binary codes from shift-invariant kernels.NIPS22 (2009)

    2009

  47. [47]

    Zhenyuan Ruan, Seo Jin Park, Marcos K Aguilera, Adam Belay, and Malte Schwarzkopf. 2023. Nu: Achieving Microsecond-Scale resource fungibility with logical processes. InNSDI. 1409–1427

    2023

  48. [48]

    Abraham Silberschatz, Henry F Korth, and Shashank Sudarshan. 2011. Database system concepts. (2011)

    2011

  49. [49]

    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

  50. [50]

    Jingkuan Song, Yi Yang, Zi Huang, Heng Tao Shen, and Richang Hong. 2011. Multiple feature hashing for real-time large scale near-duplicate video retrieval. InMM. 423–432

    2011

  51. [51]

    Robert F Sproull. 1991. Refinements to nearest-neighbor searching in k- dimensional trees.Algorithmica6 (1991), 579–589

    1991

  52. [52]

    Yongye Su, Yinqi Sun, Minjia Zhang, and Jianguo Wang. 2024. Vexless: A Server- less Vector Data Management System Using Cloud Functions.Proc. ACM Manag. Data2, 3, Article 187 (2024)

    2024

  53. [53]

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

    1980

  54. [54]

    Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. 2012. Semi-supervised hashing for large-scale search.TPAMI34, 12 (2012), 2393–2406

    2012

  55. [55]

    Jingdong Wang and Shipeng Li. 2012. Query-driven iterated neighborhood graph search for large scale indexing. InMM. 179–188

    2012

  56. [56]

    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

  57. [57]

    Jingdong Wang, Naiyan Wang, You Jia, Jian Li, Gang Zeng, Hongbin Zha, and Xian-Sheng Hua. 2013. Trinary-projection trees for approximate nearest neighbor search.TPAMI36, 2 (2013), 388–403

    2013

  58. [58]

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xi- angyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. InSIGMOD. 2614–2627

    2021

  59. [59]

    Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xi- angyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High- Dimensional Vector Similarity Search on Data Segment.SIGMOD2, 1 (2024), 1–27

    2024

  60. [60]

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

    2021

  61. [61]

    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.PVLDB13, 12 (2020), 3152–3165

    2020

  62. [62]

    Yair Weiss, Antonio Torralba, and Rob Fergus. 2008. Spectral hashing.NIPS21 (2008)

    2008

  63. [63]

    Long Xiang, Bo Tang, and Chuan Yang. 2019. Accelerating exact inner product retrieval by cpu-gpu systems. InSIGIR. 1277–1280

    2019

  64. [64]

    Chaojun Xiao, Pengle Zhang, Xu Han, Guangxuan Xiao, Yankai Lin, Zhengyan Zhang, Zhiyuan Liu, and Maosong Sun. 2024. InfLLM: Training-Free Long- Context Extrapolation for LLMs with an Efficient Context Memory. InarXiv

    2024

  65. [65]

    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

  66. [66]

    Hao Xu, Jingdong Wang, Zhu Li, Gang Zeng, Shipeng Li, and Nenghai Yu. 2011. Complementary hashing for approximate nearest neighbor search. InICCV. IEEE, 1631–1638

    2011

  67. [67]

    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. InSOSP. 545–561

    2023

  68. [68]

    Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. PASE: PostgreSQL Ultra-High- Dimensional Approximate Nearest Neighbor Search Extension. InSIGMOD. 2241–2253

    2020

  69. [69]

    Song Yu, Shengyuan Lin, Shufeng Gong, Yongqing Xie, Ruicheng Liu, Yijie Zhou, Ji Sun, Yanfeng Zhang, Guoliang Li, and Ge Yu. 2025. A Topology-Aware Localized Update Strategy for Graph-Based ANN Index.arXiv e-prints(2025), arXiv–2503

    2025

  70. [70]

    Minjia Zhang and Yuxiong He. 2019. Grip: Multi-store capacity-optimized high- performance nearest neighbor search for vector search engine. InCIKM. 1673– 1682. 13

    2019