Pith. sign in

REVIEW 2 major objections 5 minor 63 references

A lock-free GPU graph index can absorb streaming inserts and deletes without rebuilding, with proven monotone deletion and memory bounded by the live set.

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 · grok-4.5

2026-07-12 12:19 UTC pith:WISI6ZLX

load-bearing objection Solid GPU systems paper: lock-free COW slab with inlined deletion flag gives real safety proofs and large measured maintenance wins over rebuilds; navigability after repair is empirical only. the 2 major comments →

arxiv 2607.02543 v1 pith:WISI6ZLX submitted 2026-06-24 cs.DC

ETALE: Evolving Topology with Accelerated Lock-free Execution for Dynamic Graph ANN Search on GPUs

Dongfang Zhao This is my paper
classification cs.DC
keywords approximate nearest neighbor searchvector databaseGPUdynamic graph indexlock-free data structurecopy-on-writedeletion monotonicitymemory reclaim
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.

GPU graph indexes for approximate nearest-neighbor search have been static: any insert or delete forces a rebuild of the affected window. Dynamic graph indexes that update in place have lived on the CPU and left GPU parallelism unused. This paper presents ETALE, a GPU-native proximity-graph index that maintains itself under streaming insertion and deletion without a global rebuild. Its core is a lock-free copy-on-write slab structure in which each node’s deletion flag, degree, and adjacency pointer share one 64-bit word published by a single atomic compare-and-swap. That packing yields a proven deletion-monotonicity invariant (a deleted node never reappears) and a reclaim protocol whose GPU memory footprint is bounded by the live set and whose cost is sublinear in accumulated deletions under a uniform model. On five multimodal datasets under continuous 1% churn, ETALE finishes each maintenance round in hundreds of milliseconds at Recall@10 above 0.95, several to several times faster than static GPU rebuilds and far faster than CPU dynamic baselines, while its resident slabs stay pinned to the live set where tombstone-only systems grow without bound.

Core claim

ETALE shows that a proximity graph for ANN can live entirely on the GPU and absorb concurrent streaming inserts and deletes without a global rebuild, by packing deletion state and adjacency into one atomically published 64-bit word so that every adjacency rewrite is a single lock-free compare-and-swap, deletion is monotone by construction, and periodic reclaim keeps GPU memory bounded by the live set at a cost that saturates rather than grows with tombstones.

What carries the argument

Lock-free copy-on-write slab graph with a packed 64-bit node reference: each node’s deletion flag, out-degree, and slab identifier occupy one atomic word that names an immutable neighbor slab; Publish allocates a fresh slab, writes the new neighbor list, and installs the whole rewrite with one compare-and-swap that carries the deletion flag forward, so no later publication can revive a tombstone.

Load-bearing premise

Local connectivity repair around a deleted node is assumed to keep the graph navigable enough for high recall under continuous churn; that navigability is measured, not proven, so quality claims fail if repair systematically severs long-range paths on some data distributions.

What would settle it

Run the pure-deletion stress of Section 5.5 on a distribution where hub nodes dominate paths: if Recall@10 falls steadily as half the live set is deleted with only local RobustPrune repair, the navigability claim fails even while deletion monotonicity still holds.

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

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 / 5 minor

Summary. ETALE is a GPU-native graph ANN index for streaming insertion and deletion without global rebuild. Its core is a lock-free copy-on-write slab graph in which each node’s deletion flag, degree, and slab pointer share one 64-bit word published by a single CAS. From this design the paper proves deletion monotonicity (Prop. 1), no use-after-free under two-phase reclaim plus epoch separation (Prop. 2, Lemma 1), a VRAM footprint equal to the live-set size after reclaim (Prop. 3), and a reclaim cost that saturates sublinearly in accumulated tombstones under a uniform in-edge model (Prop. 4). A CUDA implementation is evaluated on five multimodal datasets against CAGRA, Tagore, HNSW, and DIGRA; under 1% continuous churn ETALE maintains the index in hundreds of milliseconds per round at Recall@10 above 0.95, 4.8–8.8× faster than CAGRA rebuilds and 1.8–2.5× faster than Tagore, while keeping memory bounded where tombstone-only systems grow.

Significance. If the results hold, ETALE closes a clear systems gap: GPU graph ANN indexes have been static (rebuild-to-update) while dynamic graph indexes have lived on the CPU. The combination of a lock-free COW slab with an inlined deletion bit, machine-checkable-style proofs of monotonicity and reclaim safety, a live-set-bounded VRAM footprint, and multi-baseline measurements at matched recall is a substantial contribution to GPU vector search and concurrent data structures. Strengths that should be credited explicitly include the clean derivation of Props. 1–3 from the packed reference and launch model, the open CUDA implementation with reproduction scripts, concurrent query/update latency results (Table 3) that support the wait-free reader claim, and the empirical saturating reclaim fit (R²=0.999) that corroborates the cost analysis.

major comments (2)
  1. §3.4.2 Algorithm 3 and §5.5–5.8: Local RobustPrune repair on the deleted node’s live neighbors is assumed to keep the proximity graph navigable enough for high recall under sustained incremental churn. Navigability after repair is not proven—only measured (flat Recall@10 under pure deletion and multi-round churn). The structural claims (deletion monotonicity, reclaim safety, bounded footprint) hold independently of navigability, so this does not falsify the central contribution; it does, however, leave open whether quality can degrade on distributions where local repair severs long-range paths. A short discussion of failure modes, or an additional stress distribution, would strengthen the quality claim without changing the proofs.
  2. §4.5 Proposition 4 and Remark 1: The sublinear reclaim argument rests on a uniform independent placement model for stranded in-edges. Remark 1 already notes that real hubs saturate dirty nodes faster than the model predicts and treats the saturating form as an empirical regularity rather than a quantitative predictor of τ. That caveat is appropriate; the proposition should be framed more clearly as a qualitative explanation of the observed saturation (and of the ceiling reclaim(t)<M) rather than as a tight predictive bound, so that readers do not over-read the model.
minor comments (5)
  1. Table 1 lists SIGMOD’26 / ICDE’24 venues for Tagore, DIGRA, and CAGRA; confirm final citation status and page numbers before camera-ready.
  2. Figure 1 and the abstract both report “hundreds of milliseconds” and 4.8–8.8×; ensure the exact per-dataset numbers in §5.3 are consistent with the figure caption (SIFT 7.1× vs. the range).
  3. §3.3: the CAS attempt budget in Publish is mentioned but not quantified in the evaluation; a one-line note on observed retry rates under the churn workload would help.
  4. Notation: R is both slab capacity and (implicitly) warp width; a brief reminder when R=32 is fixed would reduce ambiguity for readers outside GPU systems.
  5. §5.4: the large margin over DIGRA is correctly attributed to DIGRA’s range-filter design; a single sentence clarifying that the comparison is unfiltered-only would further avoid misreading.

Circularity Check

0 steps flagged

No significant circularity: structural invariants follow from the COW/CAS design by construction, and empirical claims are measured against external baselines rather than fitted inputs renamed as predictions.

full rationale

The load-bearing derivation chain is self-contained. Proposition 1 (deletion monotonicity) follows directly from packing the deletion flag into the same 64-bit word that every Publish/Delete/Reclaim CAS swaps; the proof enumerates the three operations that write r(u) and shows none can clear a set flag. Propositions 2–3 (no use-after-free; footprint = L after reclaim) follow from the two-phase Reclaim order plus epoch separation (Lemma 1) under the stated launch/execution model. Proposition 4 derives the saturating dirty-node count under an explicit uniform in-edge placement model; Corollary 1 then bounds reclaim cost by a full live-set rebuild. Remark 1 honestly demotes the model from quantitative predictor of τ to a mechanism for an empirical regularity, and §5.7 presents the M(1−e^{−t/τ}) fit as validation of shape (R²=0.999), not as a design-justifying prediction. End-to-end speedups and recall are measured against external systems (CAGRA, Tagore, HNSW, DIGRA) on public datasets. Self-citations ([54] SIVF, [55] 2009 local-repair lineage) appear only as related-work context and do not underwrite the CAS proofs or the measured claims. Navigability after RobustPrune repair is an unproven empirical assumption, not a circular step. No fitted parameter is renamed as a first-principles result, and no uniqueness theorem is imported from the authors to forbid alternatives.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 2 invented entities

The central systems claim rests on standard GPU concurrency assumptions, reuse of RobustPrune/Vamana edge selection, a hand-chosen slab width matching warp size, and an idealized uniform in-edge model used only for the sublinear-reclaim analysis. The invented structure is the packed 64-bit node reference plus epoch-separated COW slab pool; independent evidence is the CUDA implementation and measured concurrent-query stability, not an external physical prediction.

free parameters (5)
  • slab capacity R
    Fixed at 32 to match warp width; bounds out-degree and publication cost O(R). Chosen by hardware, not fitted to recall curves, but still a design constant the claims depend on.
  • RobustPrune slack α and build/search beam widths (EF_BUILD, EF_SEARCH)
    Control graph quality and query recall; §5.9 sweeps EF_SEARCH. Standard ANN knobs, not derived from first principles.
  • reclaim interval / accumulated-tombstone threshold
    Policy parameter trading peak footprint vs amortized reclaim cost; sawtooth in Fig. 5 depends on when reclaim fires.
  • CAS attempt budget in Publish
    Algorithm 1 retries until success or budget exhausted; affects liveness under extreme contention though amortized cost argument assumes progress elsewhere.
  • fitted reclaim ceiling M and time constant τ
    §5.7 fits M≈658 ms, τ≈1.6e4 tombstones to measured reclaim cost (R²=0.999). Used to illustrate saturation, not to set the algorithm; still free parameters in the empirical model.
axioms (5)
  • domain assumption GPU launch/execution model: kernels are finite concurrent thread sets; successive launches are fully serialized by device sync; retired slabs return to free pool only between launches (Definition 2, Lemma 1).
    Load-bearing for epoch separation and no use-after-free without per-slab refcounts. Standard CUDA practice but not a mathematical necessity of all GPU runtimes.
  • domain assumption Aligned 64-bit load/store/CAS on the packed node reference is atomic and the memory fence in Publish orders slab contents before the reference becomes visible (Algorithm 1; GPU relaxed memory model [1]).
    Required for wait-free readers and single-word publication of multi-entry adjacency.
  • domain assumption RobustPrune_α / Vamana-style slack pruning yields a navigable bounded-degree proximity graph under both initial build and local repair after deletion.
    Imported from DiskANN/Vamana literature; ETALE reuses it without a new navigability proof for the incremental repair path.
  • ad hoc to paper Uniform independent placement of stranded in-edges over live nodes for expected dirty-node count D(t) (Proposition 4).
    Used only for the sublinear reclaim cost shape; Remark 1 concedes hubs make τ smaller than L/d̄.
  • standard math Standard concurrent-object progress notions: readers wait-free via single atomic load; writers lock-free because a failed CAS implies another writer succeeded.
    Classic Herlihy-style reasoning applied to Publish.
invented entities (2)
  • ETALE packed 64-bit node reference r(u)=⟨δ_u, d_u, s_u⟩ with immutable COW adjacency slabs independent evidence
    purpose: Make full adjacency rewrite a single CAS and inline deletion so monotonicity is structural.
    Core data-structure invention of the paper; not present as such in cited GPU ANN indexes.
  • Two-stack free/retired slab pool with host-side recycle only at kernel boundaries independent evidence
    purpose: Reclaim GPU memory without per-slab reference counting while preserving no-use-after-free.
    Epoch discipline specialized to ETALE’s launch model; evidence is the implementation and Proposition 2.

pith-pipeline@v1.1.0-grok45 · 29281 in / 3985 out tokens · 43972 ms · 2026-07-12T12:19:38.447588+00:00 · methodology

0 comments
read the original abstract

Graph-based approximate nearest neighbor (ANN) indexes on the GPU are originally built for static collections and must reconstruct the affected window to absorb any update, while the dynamic graph indexes that update incrementally run on the CPU and cannot exploit GPU parallelism. This paper presents a new ANN index, namely ETALE (Evolving Topology with Accelerated Lock-free Execution), which is among the first GPU-native graph ANN indexes to support streaming insertion and deletion without a global rebuild. The core of ETALE is a lock-free copy-on-write slab graph whose deletion state and adjacency share a single atomically published word, which yields a provable deletion-monotonicity invariant together with a bounded reclaim of GPU memory that is sublinear in accumulated deletions. We have implemented ETALE in CUDA and evaluate it on five diverse multimodal datasets against four state-of-the-art indexes: Tagore (GPU static, SIGMOD'26), DIGRA (CPU dynamic, SIGMOD'26), CAGRA (GPU static, ICDE'24), and HNSW (CPU dynamic, TPAMI'20). Under continuous churn, ETALE maintains the index in hundreds of milliseconds per round at recall above $0.95$, which is $4.8$--$8.8\times$ faster than CAGRA's per-window rebuild, $1.8$--$2.5\times$ faster than the more recent Tagore, and $3.3$--$147\times$ faster than the CPU dynamic indexes. In addition, the memory footprint of ETALE stays bounded where tombstone-only systems grow indefinitely.

Figures

Figures reproduced from arXiv: 2607.02543 by Dongfang Zhao.

Figure 1
Figure 1. Figure 1: Maintenance under 1% churn on SIFT. Left: ETALE maintains the index incrementally at about 250 ms per round, 7.1× cheaper than CAGRA’s per-round rebuild. Right: the saving holds at quality parity, with Recall@10 of the two systems coinciding within a few thousandths across rounds. CAGRA [32], the state-of-the-art GPU index, fixes every node’s neighbor list in a single batch-oriented construction pass, so i… view at source ↗
Figure 2
Figure 2. Figure 2: The ETALE index structure. Each identifier [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Per-round maintenance under 1% churn, ETALE vs. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 3
Figure 3. Figure 3: Per-round maintenance under 1% churn on the GPU, ETALE against CAGRA and Tagore. 5.3 End-to-end Comparison with GPU Indexes We first compare ETALE against the GPU graph indexes that share its hardware, namely CAGRA [32] and Tagore [22]. CAGRA is the established state-of-the-art GPU graph index, and Tagore is a more recent GPU library that accelerates the construction of the same class of graphs. Neither ha… view at source ↗
Figure 6
Figure 6. Figure 6: Pure-deletion stress on DEEP (delete 20k/round, no insertions, to live = 100k). 100k. Recall then turns entirely on whether the delete path preserves navigability [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 8
Figure 8. Figure 8: Recall@10 over churn rounds stays flat as inserts [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 7
Figure 7. Figure 7: Reclaim cost vs. accumulated tombstones. [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: Parameter sensitivity of ETALE on DEEP [PITH_FULL_IMAGE:figures/full_fig_p012_9.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

63 extracted references · 7 canonical work pages

  1. [1]

    Donaldson, Ganesh Gopalakrishnan, Jeroen Ketema, Daniel Poetzl, Tyler Sorensen, and John Wickerson

    Jade Alglave, Mark Batty, Alastair F. Donaldson, Ganesh Gopalakrishnan, Jeroen Ketema, Daniel Poetzl, Tyler Sorensen, and John Wickerson. 2015. GPU Concur- rency: Weak Behaviours and Programming Assumptions.SIGPLAN Not.50, 4 (March 2015), 577–591. doi:10.1145/2775054.2694391

    work page doi:10.1145/2775054.2694391 2015

  2. [2]

    Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Dis- tance. InAdvances in Neural Information Processing Systems, C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (Eds.), Vol. 28. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2015/file/ 28...

    2015

  3. [3]

    Zeki Yalniz

    Dmitry Baranchuk, Matthijs Douze, Yash Upadhyay, and I. Zeki Yalniz. 2023. DeDrift: Robust Similarity Search under Content Drift. In2023 IEEE/CVF In- ternational Conference on Computer Vision (ICCV). 10992–11001. doi:10.1109/ ICCV51070.2023.01012

    arXiv 2023

  4. [4]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching.Commun. ACM18, 9 (Sept. 1975), 509–517. doi:10.1145/361002.361007

    doi:10.1145/361002.361007 1975

  5. [5]

    Blelloch, Daniel Anderson, and Laxman Dhulipala

    Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Archi- tectures(Virtual Event, USA)(SPAA ’20). Association for Computing Machinery, New York, NY, USA, 507–509. doi:10.1145/3350755.3400254

    doi:10.1145/3350755.3400254 2020

  6. [6]

    Mirrokni

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. InProceedings of the Twentieth Annual Symposium on Computational Geometry(Brooklyn, New York, USA)(SCG ’04). Association for Computing Machinery, New York, NY, USA, 253–262. doi:10.1145/997817.997857

    doi:10.1145/997817.997857 2004

  7. [7]

    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(Hyderabad, India)(WWW ’11). Association for Computing Machinery, New York, NY, USA, 577–586. doi:10.1145/1963405. 1963487

    work page doi:10.1145/1963405 2011

  8. [8]

    Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2025. The Faiss library. arXiv:2401.08281 [cs.LG] https://arxiv.org/abs/2401.08281

    Pith/arXiv arXiv 2025

  9. [9]

    Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. arXiv:1609.07228 [cs.CV] https://arxiv.org/abs/1609.07228

    Pith/arXiv arXiv 2016

  10. [10]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph.Proc. VLDB Endow.12, 5 (Jan. 2019), 461–474. doi:10.14778/3303753.3303754

    doi:10.14778/3303753.3303754 2019

  11. [11]

    Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search.Proc. ACM Manag. Data2, 3, Article 167 (May 2024), 27 pages. doi:10. 1145/3654970

    2024

  12. [12]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization.IEEE Trans. Pattern Anal. Mach. Intell.36, 4 (April 2014), 744–755. doi:10.1109/TPAMI.2013.240

    doi:10.1109/tpami.2013.240 2014

  13. [13]

    Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premku- mar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. Filtered- DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. InProceedings of the ACM Web Conference 2023(Aust...

    doi:10.1145/3543507.3583552 2023

  14. [14]

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. InProceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119), Hal Daumé III and Aarti Singh (Eds.). PMLR, 3887–3896. http...

    2020

  15. [15]

    Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)

    2016

  16. [16]

    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(Dallas, Texas, USA)(STOC ’98). Association for Computing Machinery, New York, NY, USA, 604–613. doi:10.1145/276698. 276876

    doi:10.1145/276698 1998

  17. [17]

    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. InAdvances in Neural Information Pro- cessing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran As...

    2019

  18. [18]

    Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Guanhao Hou, Jieming Shi, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter.Proc. ACM Manag. Data3, 3, Article 148 (June 2025), 26 pages. doi:10.1145/3725399

    doi:10.1145/3725399 2025

  19. [19]

    Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search.IEEE Transactions on Pattern Analysis and Machine Intelligence33, 1 (2011), 117–128. doi:10.1109/TPAMI.2010.57

    doi:10.1109/tpami.2010.57 2011

  20. [20]

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-augmented generation for knowledge-intensive NLP tasks. InProceedings of the 34th Inter- national Conference on Neural Information Processing Systems(V...

    2020

  21. [21]

    Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement.IEEE Transactions on Knowl- edge and Data Engineering32, 8 (2020), 1475–1488. doi:10.1109/TKDE.2019. 2909204

    doi:10.1109/tkde.2019 2020

  22. [22]

    Zhonggen Li, Xiangyu Ke, Yifan Zhu, Bocheng Yu, Baihua Zheng, and Yunjun Gao

  23. [23]

    ACM Manag

    Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search.Proc. ACM Manag. Data3, 6, Article 360 (Dec. 2025), 27 pages. doi:10. 1145/3769825

    2025

  24. [24]

    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.Proc. VLDB Endow.18, 7 (March 2025), 2268–2280. doi:10.14778/3734839.3734860

    doi:10.14778/3734839.3734860 2025

  25. [25]

    Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi- probe LSH: efficient indexing for high-dimensional similarity search. InPro- ceedings of the 33rd International Conference on Very Large Data Bases(Vienna, Austria)(VLDB ’07). VLDB Endowment, 950–961

    2007

  26. [26]

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

  27. [27]

    doi:10.1016/j.is.2013.10.006

    Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems45 (2014), 61–68. doi:10.1016/j.is.2013.10.006

    doi:10.1016/j.is.2013.10.006 2014

  28. [28]

    Malkov and D

    Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell.42, 4 (April 2020), 824–836. doi:10.1109/ TPAMI.2018.2889473

    arXiv 2020

  29. [29]

    Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms. InProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming(Edinburgh, United Kin...

    doi:10.1145/3627535.3638475 2024

  30. [30]

    Hoos, and James J

    Julieta Martinez, Shobhit Zakhmi, Holger H. Hoos, and James J. Little. 2018. LSQ++: Lower running time and higher recall in multi-codebook quantization. InProceedings of the European Conference on Computer Vision (ECCV)

    2018

  31. [31]

    Ellis, and Gert R.G

    Brian McFee, Thierry Bertin-Mahieux, Daniel P.W. Ellis, and Gert R.G. Lanck- riet. 2012. The million song dataset challenge. InProceedings of the 21st In- ternational Conference on World Wide Web(Lyon, France)(WWW ’12 Com- panion). Association for Computing Machinery, New York, NY, USA, 909–916. doi:10.1145/2187980.2188222

    doi:10.1145/2187980.2188222 2012

  32. [32]

    Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data .IEEE Transactions on Pattern Analysis & Machine Intelligence36, 11 (Nov. 2014), 2227–2240. doi:10.1109/TPAMI.2014.2321376

    doi:10.1109/tpami.2014.2321376 2014

  33. [33]

    Naoki Ono and Yusuke Matsui. 2023. Relative NN-Descent: A Fast Index Con- struction for Graph-Based Approximate Nearest Neighbor Search. InProceedings of the 31st ACM International Conference on Multimedia(Ottawa ON, Canada) (MM ’23). Association for Computing Machinery, New York, NY, USA, 1659–1667. doi:10.1145/3581783.3612290

    doi:10.1145/3581783.3612290 2023

  34. [34]

    Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2024. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs . In2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE Computer Society, Los Alamitos, CA, USA, 4236–4247. doi:10.1109/ICDE60146.2024.00323

    doi:10.1109/icde60146.2024.00323 2024

  35. [35]

    Yu Pan, Jianxin Sun, and Hongfeng Yu. 2023. LM-DiskANN: Low Memory Foot- print in Disk-Native Dynamic Graph-Based ANN Indexing. InIEEE International Conference on Big Data, BigData 2023, Sorrento, Italy, December 15-18, 2023, Jingrui He, Themis Palpanas, Xiaohua Hu, Alfredo Cuzzocrea, Dejing Dou, Dominik Slezak, Wei Wang, Aleksandra Gruca, Jerry Chun-Wei ...

    doi:10.1109/bigdata59044.2023.10386517 2023

  36. [36]

    Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Struc- tured Data.Proc. ACM Manag. Data2, 3, Article 120 (May 2024), 27 pages. doi:10.1145/3654923

    doi:10.1145/3654923 2024

  37. [37]

    Runwen Qiu and Jing Tang. 2025. Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph.Proc. ACM Manag. Data3, 6, Article 321 (Dec. 2025), 26 pages. doi:10.1145/3769786 13 Dongfang Zhao

    work page doi:10.1145/3769786 2025

  38. [38]

    Jiancheng Ruan, Tingyang Chen, Renchi Yang, Xiangyu Ke, and Yunjun Gao. 2025. Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities. InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2(Toronto ON, Canada)(KDD ’25). Association for Computing Machinery, New York, NY, USA, 2444–...

    arXiv 2025

  39. [39]

    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:2105.09613 [cs.IR] https://arxiv.org/abs/2105.09613

    Pith/arXiv arXiv 2021

  40. [40]

    Yiping Sun, Yang Shi, and Jiaolong Du. 2024. A Real-Time Adaptive Multi- Stream GPU System For Online Approximate Nearest Neighborhood Search. InProceedings of the 33rd ACM International Conference on Information and Knowledge Management(Boise, ID, USA)(CIKM ’24). Association for Computing Machinery, New York, NY, USA, 4906–4913. doi:10.1145/3627673.3680054

    work page doi:10.1145/3627673.3680054 2024

  41. [41]

    Gonçalves, Zanoni Dias, and Ricardo da S

    Javier Vargas Muñoz, Marcos A. Gonçalves, Zanoni Dias, and Ricardo da S. Torres

  42. [42]

    2019), 10 pages

    Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search.Pattern Recogn.96, C (Dec. 2019), 10 pages. doi:10.1016/j.patcog. 2019.106970

    doi:10.1016/j.patcog 2019

  43. [43]

    Karthik Venkatasubba, Saim Khan, Somesh Singh, Harsha Vardhan Simhadri, and Jyothi Vedurada. 2025. BANG: Billion-Scale Approximate Nearest Neighbour Search Using a Single GPU.IEEE Transactions on Big Data11, 6 (2025), 3142–3157. doi:10.1109/TBDATA.2025.3581085

    doi:10.1109/tbdata.2025.3581085 2025

  44. [44]

    Hui Wang, Wan-Lei Zhao, Xiangxiang Zeng, and Jianye Yang. 2021. Fast k-NN Graph Construction by GPU based NN-Descent. InProceedings of the 30th ACM International Conference on Information & Knowledge Management(Virtual Event, Queensland, Australia)(CIKM ’21). Association for Computing Machinery, New York, NY, USA, 1929–1938. doi:10.1145/3459637.3482344

    doi:10.1145/3459637.3482344 2021

  45. [45]

    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. InProceedings of the 202...

    doi:10.1145/3448016.3457550 2021

  46. [46]

    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.Proc. ACM Manag. Data2, 1, Article 14 (March 2024), 27 pages. doi:10.1145/3639269

    doi:10.1145/3639269 2024

  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.Proc. VLDB Endow.14, 11 (July 2021), 1964–1978. doi:10.14778/3476249.3476255

    doi:10.14778/3476249.3476255 2021

  48. [48]

    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.Proc. VLDB Endow.13, 12 (Aug. 2020), 3152–3165. doi:10.14778/3415478.3415541

    doi:10.14778/3415478.3415541 2020

  49. [49]

    Bernstein, Badrish Chan- dramouli, Richard Wen, and Harsha Vardhan Simhadri

    Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chan- dramouli, Richard Wen, and Harsha Vardhan Simhadri. 2025. In-Place Up- dates of a Graph Index for Streaming Approximate Nearest Neighbor Search. arXiv:2502.13826 [cs.IR] https://arxiv.org/abs/2502.13826

    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, Peng Cheng, and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. InProceedings of the 29th Symposium on Operating Systems Principles(Koblenz, Germany)(SOSP ’23). Association for Computing Machinery, New York...

    arXiv 2023

  51. [51]

    Artem Babenko Yandex and Victor Lempitsky. 2016. Efficient Indexing of Billion- Scale Datasets of Deep Descriptors. In2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055–2063. doi:10.1109/CVPR.2016.226

    doi:10.1109/cvpr.2016.226 2016

  52. [52]

    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.Proc. VLDB Endow.18, 6 (Feb. 2025), 1825–1838. doi:10.14778/3725688.3725709

    doi:10.14778/3725688.3725709 2025

  53. [53]

    Hamilton, and Jure Leskovec

    Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. InProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining(London, United Kingdom) (KDD ’18). Association for Computing Machinery, New York, NY, ...

    doi:10.1145/3219819.3219890 2018

  54. [54]

    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.Proc. VLDB Endow.19, 3 (Nov. 2025), 495–508. doi:10.14778/3778092.3778108

    doi:10.14778/3778092.3778108 2025

  55. [55]

    Yuanhang Yu, Dong Wen, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2022. GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction . In2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE Computer Society, Los Alamitos, CA, USA, 552–564. doi:10.1109/ICDE53745.2022.00046

    doi:10.1109/icde53745.2022.00046 2022

  56. [56]

    Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou

  57. [57]

    In17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)

    VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 377–395. https://www.usenix.org/conference/osdi23/presentation/zhang-qianxi

  58. [58]

    Dongfang Zhao. 2026. SIVF: GPU-Resident IVF Index for Streaming Vector Analytics. InProceedings of the 35th International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’26)(Cleveland, OH, USA). Association for Computing Machinery, New York, NY, USA, 1–14. doi:10.1145/3806645. 3807575

    work page doi:10.1145/3806645 2026

  59. [59]

    Dongfang Zhao and Li Yang. 2009. Incremental Isometric Embedding of High- Dimensional Data Using Connected Neighborhood Graphs.IEEE Trans. Pattern Anal. Mach. Intell.31, 1 (Jan. 2009), 86–98. doi:10.1109/TPAMI.2008.34

    work page doi:10.1109/tpami.2008.34 2009

  60. [60]

    Weijie Zhao, Shulong Tan, and Ping Li. 2020. SONG: Approximate Near- est Neighbor Search on GPU. In36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020. IEEE, 1033–1044. doi:10.1109/ICDE48307.2020.00094

    doi:10.1109/icde48307.2020.00094 2020

  61. [61]

    Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High- Dimensional Spaces.Proc. VLDB Endow.16, 8 (April 2023), 1979–1991. doi:10. 14778/3594512.3594527

    arXiv 2023

  62. [62]

    Yifan Zhu, Ruiyao Ma, Baihua Zheng, Xiangyu Ke, Lu Chen, and Yunjun Gao

  63. [63]

    ACM Manag

    GTS: GPU-based Tree Index for Fast Similarity Search.Proc. ACM Manag. Data2, 3, Article 142 (May 2024), 27 pages. doi:10.1145/3654945 14

    work page doi:10.1145/3654945 2024