Pith. sign in

REVIEW 4 major objections 4 minor 41 references

A merged query–data index gives vector joins a constant-time starting point, cutting latency by up to 56x.

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-02 18:02 UTC pith:XMY2VYH2

load-bearing objection Worth your time: three genuinely new mechanisms for batch vector joins, but the headline 'constant-time start' claim is stronger than the merged-index construction supports — fixable with one measurement. the 4 major comments →

arxiv 2603.16360 v2 pith:XMY2VYH2 submitted 2026-03-17 cs.DB

Fast Approximate Vector Joins via Offline-Online Co-Design

Kyoungmin Kim , Lennart Roth , Liang Liang , Anastasia Ailamaki This is my paper
classification cs.DB
keywords approximate vector jointhreshold-based joinwork sharingmerged indexrelative neighborhood graphout-of-distribution querieshybrid searchgraph-based ANN index
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 aims to show that approximate threshold-based vector joins—finding all vector pairs within a distance threshold—can be made dramatically faster by reusing traversal work across similar queries and by moving the hardest step, finding one in-range point per query, into offline index construction. It proposes three mechanisms: soft work sharing, which caches the closest visited point even when it is outside the threshold; a merged index over queries and data, which lets each query start from a near neighbor in roughly constant time; and an adaptive hybrid search that bridges disconnected in-range regions for out-of-distribution queries. On eight datasets, the combined approach improves the efficiency–recall trade-off over the prior state of the art, with latency reductions up to 56.3x and recall gains up to 43% on out-of-distribution-heavy workloads. If correct, this gives database systems a practical blueprint for embedding vector joins as a first-class, hash-join-like operator.

Core claim

The paper's central claim is that a threshold-based vector join can be split into two phases—finding an initial in-range point for each query, then expanding to all reachable in-range points—and that the first phase can be almost eliminated by building a single graph index over both query and data vectors. In that merged index, a query's own neighbors are likely to include its nearest data point, thanks to the relative-neighborhood-graph property that an exact RNG connects every point to its closest neighbor; practical indexes such as NSG and HNSW approximate this property. Hence the query can seed its traversal by directly inspecting its neighbors in the merged index, instead of running a g

What carries the argument

The central object is the merged index G_{X∪Y}: one proximity graph built over both query and data vectors. It gives each query a near-constant-time seed, because graph indexes approximate a relative neighborhood graph—an edge exists when no third point lies closer to both endpoints—so a point's neighbors are expected to include its closest point. The paper also uses soft work sharing, caching only the closest visited point per query even when out-of-range, and an adaptive hybrid BFS/BestFS search that crosses out-of-range nodes for queries flagged out-of-distribution by a 1.5x distance-ratio heuristic.

Load-bearing premise

The constant-time start depends on the merged graph genuinely containing an edge from each query to its nearest data point; NSG and HNSW only approximate the relative-neighborhood graph, so there is no guarantee, and the approximation is weakest exactly for out-of-distribution queries where the paper observes recall drops.

What would settle it

Measure the fraction of queries whose true nearest data point appears in the query node's neighbor list in the merged NSG or HNSW index. If that fraction is well below 1 for typical in-distribution queries, or falls as data scale grows, the claimed O(1) seed justification collapses and the speedups would rest on heuristic seeding rather than a proven relative-neighborhood property. The paper does not report this measurement.

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

If this is right

  • Threshold-based vector joins can adopt the cost model of relational hash joins: the first in-range point per query is found in roughly constant time, turning the operator's online cost into the cost of an expanding BFS.
  • Caching a single out-of-range closest point per query is enough to propagate traversal effort between similar queries, reducing memory usage substantially when thresholds are large compared to caching all in-range results.
  • Adaptive hybrid search lets an unmodified proximity graph recover most of the recall loss on out-of-distribution workloads, removing the need for special OOD index structures in the threshold-join setting.
  • The techniques transfer across graph index types (NSG and HNSW), so existing ANN infrastructure can absorb them without new index designs.
  • Combined, the mechanisms yield sub-linear join-latency growth as data scales to 10 million vectors, pointing toward billion-scale viability with distributed execution.

Where Pith is reading between the lines

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

  • The O(1) start claim is only as strong as the RNG approximation: an index-agnostic test—measuring what fraction of queries have their true nearest data point among their graph neighbors—would directly validate the offloading argument, and that fraction is likely to drop for out-of-distribution queries.
  • The same merged-index idea could extend to self-joins and filtered (metadata-constrained) joins, since the index already contains both sides and selection predicates could shrink the seed set before traversal; the paper gestures at filtered vector search but does not test it.
  • The 1.5x distance-ratio heuristic for flagging OOD queries is a fixed threshold; calibrating it per dataset or replacing it with a learned model might tighten the reported latency–recall trade-off.
  • If the constant-time-seed behavior holds at scale, query optimizers could treat vector joins as pipelined operators with predictable per-query cost, enabling cost-based plans for mixed vector-relational workloads—a direction the paper lists as future work but does not establish.

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

4 major / 4 minor

Summary. The paper presents a unified framework for approximate threshold-based vector joins. It proposes three main techniques: (1) soft work sharing, which caches the closest available data point per query even when it is outside the join threshold; (2) a merged index built over both query and data vectors, intended to give each query a constant-time starting point for the join by exploiting relative-neighborhood-graph properties; and (3) an adaptive hybrid BFS/BestFS search for out-of-distribution queries. The framework is implemented on NSG and HNSW and evaluated on eight datasets, with experiments reporting large latency improvements over a re-implemented SimJoin baseline. The paper's central theoretical claim is that the merged index offloads the greedy search phase to offline construction, achieving an O(1)-type lookup of an initial in-range data point, analogous to a relational hash join.

Significance. The ideas are practical and clearly presented: soft work sharing is a natural generalization of SimJoin, and the merged-index plus hybrid-search design is a plausible direction for improving join efficiency and robustness. The paper also provides an artifact link and is transparent about some limitations, such as the re-implemented baseline. However, the central 'constant-time' guarantee is not justified by the stated RNG property for a graph that contains both query and data nodes, and the experimental validation lacks repeated-run statistics and sensitivity analyses for several key parameters. If the claims are appropriately reframed as heuristics and backed by direct measurements, the contributions could still be valuable, but in the current form the load-bearing claims are not established.

major comments (4)
  1. [§4.4, Algorithm 1] The claim that the merged index G_{X∪Y} gives each query O(1) access to an in-range data point is not supported by the stated RNG property. The exact RNG property guarantees only that the globally closest point in X∪Y is a neighbor of the query node x; that closest point may be another query vector, not a data vector in Y. Because query nodes are part of the navigational graph, the first in-range data point may be several hops away. Moreover, NSG/HNSW are explicitly described as approximations to RNG, so even the weaker property is not guaranteed. The text itself acknowledges this by saying data points in N_x are 'likely' to be close. The paper should either prove a concrete condition under which the guarantee holds (e.g., a graph built on Y with queries attached to their nearest data points), or weaken the 'constant-time' language and instead report a direct measurement: for each datase
  2. [§5.1.2, footnote 1] The comparison against SimJoin is undermined by the fact that the baseline is a re-implementation with modifications. The footnote states that the original code and index parameters were not disclosed, and that the authors modified the algorithm to avoid duplicate distance computations. The claimed speedups (up to 56.3x in §5.2.1) depend on the performance of this re-implementation. If the modified version is slower than the original SimJoin, the reported improvements are inflated. The authors should release the exact baseline code and configuration, and provide evidence that their re-implementation matches the original paper's published latency-recall behavior on at least three datasets. Alternatively, if the original code is publicly available, a direct comparison should be run.
  3. [§5.2, Figures 10-15] The experimental results appear to be based on single runs. No repeated-run statistics (mean, standard deviation, confidence intervals) are reported for latency, which is notoriously noisy in graph-based ANN systems. The paper reports speedups of tens of times (e.g., 56.3x, 32.6x) without quantifying run-to-run variance. Please report means and standard deviations over at least 5 runs, and clarify whether memory usage and indexing time are also from single runs. This is a minimum standard for a systems paper claiming large performance improvements.
  4. [§4.5, Table 1] The OOD prediction heuristic uses an arbitrary multiplier of 1.5 (d1 > 1.5 × d2). The paper does not analyze how sensitive the recall/latency trade-off is to this value, nor whether the OOD ratios reported in Table 1 are stable across reasonable variations. Since the adaptive hybrid is one of the three main contributions, the authors should provide a sensitivity analysis, e.g., sweep the ratio over {1.1, 1.3, 1.5, 2.0, 2.5} on a couple of in-distribution and OOD-heavy datasets, and show the resulting recall and latency. The early-stopping plateau length (10 iterations in §4.1) is also unexplained and unexamined.
minor comments (4)
  1. [Algorithm 4] The procedure is introduced as 'BBFS' but the algorithm name is JoinSingleQueryHybrid. Also, Q is used both as a priority queue (in the greedy phase) and as a deque with back() in lines 2 and 14; please make the data structure explicit and avoid name collision with the priority queue Q in Algorithm 2.
  2. [Algorithm 2, lines 29-42] The BFS phase uses a list B with pop(), but the text calls it a BFS queue. Please make the FIFO semantics explicit, and clarify how visited nodes are handled when a query node is popped (since the merged index contains query nodes).
  3. [Figure 10] With seven thresholds and three metrics per dataset, the figure is dense and hard to read in print. Consider splitting latency, recall, and memory into separate panels or using a log-scale-friendly layout.
  4. [Abstract] The abstract promises 'substantial improvements' but gives no quantitative anchor. The introduction lists specific numbers (up to 32.6x, 43%); consider moving one or two headline numbers to the abstract.

Circularity Check

0 steps flagged

No significant circularity: central claims are evaluated on external benchmarks, and the RNG-based justification is an independent theorem whose approximation gap is a correctness issue, not a circular reduction.

full rationale

The paper's derivation chain is not circular. The main efficiency claims (soft work sharing, merged index, adaptive BBFS) are implemented as algorithms in Section 4 and measured against exact NLJ ground truth on eight external datasets from ANN-Benchmarks/VIBE; the reported latency/recall numbers are experimental outcomes, not quantities fitted from the same constants and then relabeled as predictions. The merged-index 'constant-time' starting-point claim in Section 4.4 is justified by the relative-neighborhood graph property of Toussaint [34], an independent external theorem, not by an author-uniqueness argument or self-citation. The paper explicitly acknowledges that NSG/HNSW are only 'approximations to RNG' and that ES+MI 'often shows low recall' for OOD queries; this is a limitation of the approximation and a correctness/robustness gap, not a circular equivalence. Self-citations ([12], [31]) appear only in related-work context and are not load-bearing; core citations [16], [28], [34], [38], [41] are external. The OOD heuristic (1.5x) and the per-dataset threshold grids are heuristic/experimental choices without sensitivity analysis, which is a robustness concern, not a fitted-input-called-prediction circularity. No step in the paper defines its output in terms of its input or reduces a predicted result to a fitted parameter by construction.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 0 invented entities

The central algorithmic claim rests on (i) the RNG theorem applied to approximate graphs, (ii) the assumption that the query workload is predefined and indexable, and (iii) a set of hand-tuned parameters (OOD ratio 1.5, early-stopping plateau 10, queue size 256). No new physical entities are introduced. The merged index is a data-structure choice, not an invented entity.

free parameters (5)
  • OOD detection ratio = 1.5
    Section 4.5.3: a query is OOD if d1 > 1.5 × d2; no sensitivity analysis or ground-truth validation.
  • Early-stopping plateau length = 10
    Section 4.1: terminate greedy search if best distance plateaus for 'e.g., 10' iterations; arbitrary.
  • Max search queue size L = 256
    Used in Algorithms 2/4 and Fig 11 to generate latency-recall curves; a fixed default from [41]/[38].
  • NSG graph hyperparameters = max neighborhood 70, etc.
    Kept constant across methods (Section 5.1.2); affects traversal behavior and recall.
  • Per-dataset threshold grids = Table 2 values
    Seven thresholds per dataset selected by the authors to span small to large join sizes; the headline 'small-threshold' speedups are conditional on this choice.
axioms (5)
  • standard math If v is the closest point to u, then in an exact RNG, (u,v) is an edge.
    Used in Section 4.4 to argue the merged index contains the nearest data point as a neighbor of each query; true for exact RNG only.
  • domain assumption NSG and HNSW approximate RNG well enough to retain the top-1 edge for arbitrary queries.
    Section 4.4: 'Recent graph-based indexes ... are approximations to RNG, i.e., connecting each point to its approximate top-1 closest point.' The O(1) offloading claim and the MI speedups rely on this.
  • domain assumption Queries are a pre-defined batch set with an index, as in SimJoin.
    Definition 1/2 and Section 2.1 assume |X|≤|Y|, a predefined index on queries, and batch execution; the whole work-sharing framework depends on it.
  • domain assumption The OOD heuristic d1 > 1.5 × d2 correctly separates ID from OOD queries.
    Section 4.5.3: the paper fixes the ratio at 1.5 and provides no sensitivity analysis or ground-truth validation of the classifier.
  • domain assumption The self-implemented SimJoin baseline faithfully represents the published algorithm.
    Section 3 footnote: original authors refused code; the authors modified the algorithm 'for clarity and correctness' and verified only that per-query latency is similar (~1ms), not that indices and thresholds match.

pith-pipeline@v1.3.0-alltime-deepseek · 18526 in / 17291 out tokens · 152222 ms · 2026-08-02T18:02:11.745207+00:00 · methodology

0 comments
read the original abstract

Vector joins - finding all vector pairs between a set of query and data vectors whose distances are below a given threshold - are fundamental to modern vector and vector-relational database systems that power multimodal retrieval and semantic analytics. Existing state-of-the-art approach exploits work sharing among similar queries but still suffers from redundant index traversals and excessive distance computations. We propose a unified framework for efficient approximate vector joins that (1) introduces soft work sharing to reuse traversal results beyond the join results of previous queries, (2) builds a merged index over both query and data vectors to further speedup graph explorations, (3) improves robustness for out-of-distribution queries through an adaptive hybrid search strategy, and (4) further optimizes all these as offloading only the necessary online overhead to offline while minimizing maintenance cost. Experiments on eight datasets demonstrate substantial improvements in efficiency-recall trade-off over the state of the art.

Figures

Figures reproduced from arXiv: 2603.16360 by Anastasia Ailamaki, Kyoungmin Kim, Lennart Roth, Liang Liang.

Figure 1
Figure 1. Figure 1: Vector join procedure for a single query vector. The [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Vector join procedure for two queries, one in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of a common pruning rule used in [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: Vector join procedures for two types of indexes. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Cumulative distributions of number of data vectors [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of predicting whether a query is OOD. [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: T-SNE visualization of SIFT (left) and LAION (right), highlighting an example query (red) and it’s in-range data points (blue). 5.1.2 Baselines. We implemented all baselines within our unified vector join framework (Section 3) to ensure a fair comparison and isolate the effects of work sharing and work offloading. We also im￾plemented the state-of-the-art threshold-based vector join baseline, 8 [PITH_FULL… view at source ↗
Figure 9
Figure 9. Figure 9: Join size per dataset and threshold. SimJoin [38], inside our framework and achieved similar efficiency with their paper. This allows us to fairly assess how our techniques improve over state-of-the-art work sharing. • Naive (NLJ): A nested-loop join that computes all pairwise distances between queries 𝑋 and data 𝑌, serving as the exact but impractical baseline. • Index: Index nested-loop join (INLJ), wher… view at source ↗
Figure 10
Figure 10. Figure 10: Vector join performance (latency, recall, and memory usage) on seven thresholds and eight datasets. [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Latency-recall curves for varying queue sizes from 8 to 512. Smallest threshold, [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Latency breakdown for FMNIST into three phases: greedy search, BFS (or hybrid BBFS), and the others. Similar results observed for the other datasets. search only affects the online phase, thus is also orthogonal to designing new index structures. Recently, DARTH [8] proposed an early stopping mechanism for best-first search based on estimated recall using an ML model that predicts when further traversal y… view at source ↗
Figure 13
Figure 13. Figure 13: Offline overheads (index size and indexing time) [PITH_FULL_IMAGE:figures/full_fig_p012_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Scalability analysis on subsets of SIFT1B dataset [PITH_FULL_IMAGE:figures/full_fig_p012_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Vector join performance (latency, recall, and mem [PITH_FULL_IMAGE:figures/full_fig_p012_15.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

41 extracted references · 7 linked inside Pith

  1. [1]

    pgvector: Open-source vector similarity search for PostgreSQL

    [n.d.]. pgvector: Open-source vector similarity search for PostgreSQL. https: //github.com/pgvector. Accessed: 2025-10-16

    2025

  2. [2]

    Pinecone: a vector database

    [n.d.]. Pinecone: a vector database. https://www.pinecone.io/. Accessed: 2025- 10-16

    2025

  3. [3]

    Qdrant: Vector Database

    [n.d.]. Qdrant: Vector Database. https://qdrant.tech/. Accessed: 2025-10-16

    2025

  4. [4]

    Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, and Ion Stoica. 2013. BlinkDB: queries with bounded errors and bounded response times on very large data. InProceedings of the 8th ACM European conference on computer systems. 29–42

    2013

  5. [5]

    Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting the inverted indices for billion-scale approximate nearest neighbors. InProceedings of the European Conference on Computer Vision (ECCV). 202–216. 12

    2018

  6. [6]

    Erik Bernhardsson, Martin Aumüller, and Alexander Faithfull. 2025. ANN- Benchmarks: Benchmarks of Approximate Nearest Neighbor Libraries in Python. https://github.com/erikbern/ann-benchmarks/. Accessed: 2025-10-15

    2025

  7. [7]

    Christian Böhm, Stefan Berchtold, and Daniel A Keim. 2001. Searching in high- dimensional spaces: Index structures for improving the performance of multime- dia databases.ACM Computing Surveys (CSUR)33, 3 (2001), 322–373

    2001

  8. [8]

    Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. 2025. DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search.Proceedings of the ACM on Management of Data3, 4 (2025), 1–26

    2025

  9. [9]

    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.Proceedings of the VLDB Endowment17, 12 (2024), 3772–3785

    2024

  10. [10]

    Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X Sean Wang. 2024. RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search.Proceedings of the VLDB Endowment17, 11 (2024), 2735–2749

    2024

  11. [11]

    Yanqi Chen, Xiao Yan, Alexandra Meliou, and Eric Lo. 2025. DiskJoin: Large-scale Vector Similarity Join with SSD.arXiv preprint arXiv:2508.18494(2025)

    arXiv 2025

  12. [12]

    Yannis Chronis, Helena Caminal, Yannis Papakonstantinou, Fatma Özcan, and Anastasia Ailamaki. 2025. Filtered vector search: State-of-the-art and research opportunities.Proceedings of the VLDB Endowment18, 12 (2025), 5488–5492

    2025

  13. [13]

    Akash Das Sarma, Yeye He, and Surajit Chaudhuri. 2014. Clusterjoin: A similarity joins framework using map-reduce.Proceedings of the VLDB Endowment7, 12 (2014), 1059–1070

    2014

  14. [14]

    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. 253–262

    2004

  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, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast approximate nearest neighbor search with the navigating spreading-out graph.arXiv preprint arXiv:1707.00143(2017)

    Pith/arXiv arXiv 2017

  17. [17]

    Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. InProceedings of the 2012 ACM SIGMOD international conference on management of data. 541–552

    2012

  18. [18]

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. InInternational Conference on Machine Learning. PMLR, 3887–3896

    2020

  19. [19]

    Joseph M Hellerstein, Peter J Haas, and Helen J Wang. 1997. Online aggregation. InProceedings of the 1997 ACM SIGMOD international conference on Management of data. 171–182

    1997

  20. [20]

    Stratos Idreos, Olga Papaemmanouil, and Surajit Chaudhuri. 2015. Overview of data exploration techniques. InProceedings of the 2015 ACM SIGMOD international conference on management of data. 277–281

    2015

  21. [21]

    Elias Jääsaari, Ville Hyvönen, Matteo Ceccarello, Teemu Roos, and Martin Aumüller. 2025. VIBE: Vector Index Benchmark for Embeddings.arXiv preprint arXiv:2505.17810(2025)

    Pith/arXiv arXiv 2025

  22. [22]

    Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, and Chidambaram Crushev. 2021. A survey on locality sensitive hashing algorithms and their applications.arXiv preprint arXiv:2102.08942(2021)

    Pith/arXiv arXiv 2021

  23. [23]

    Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, and Sheshansh Agrawal. 2022. Ood-diskann: Efficient and scalable graph anns for out-of-distribution queries.arXiv preprint arXiv:2211.12850(2022)

    Pith/arXiv arXiv 2022

  24. [24]

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

    2019

  25. [25]

    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

  26. [26]

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs.IEEE Transactions on Big Data7, 3 (2019), 535–547

    2019

  27. [27]

    Hai Lan, Shixun Huang, Zhifeng Bao, and Renata Borovica-Gajic. 2024. Cardi- nality estimation for similarity search on high-dimensional data objects: The impact of reference objects.Proceedings of the VLDB Endowment18, 3 (2024), 544–556

    2024

  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]

    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, 4236–4247

    2024

  30. [30]

    Mark Raasveldt and Hannes Mühleisen. 2019. Duckdb: an embeddable analytical database. InProceedings of the 2019 international conference on management of data. 1981–1984

    2019

  31. [31]

    Viktor Sanca and Anastasia Ailamaki. 2024. Efficient Data Access Paths for Mixed Vector-Relational Search. InProceedings of the 20th International Workshop on Data Management on New Hardware. 1–9

    2024

  32. [32]

    P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. InProceedings of the 1979 ACM SIGMOD international conference on Management of data. 23–34

    1979

  33. [33]

    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

  34. [34]

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

    1980

  35. [35]

    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

  36. [36]

    Ye Wang, Ahmed Metwally, and Srinivasan Parthasarathy. 2013. Scalable all- pairs similarity search in metric spaces. InProceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining. 829–837

    2013

  37. [37]

    Yifan Wang, Vyom Pathak, and Daisy Zhe Wang. 2024. Xling: A Learned Filter Framework for Accelerating High-Dimensional Approximate Similarity Join. arXiv preprint arXiv:2402.13397(2024)

    Pith/arXiv arXiv 2024

  38. [38]

    Jiadong Xie, Jeffrey Xu Yu, and Yingfan Liu. 2025. Fast Approximate Similarity Join in Vector Databases.Proceedings of the ACM on Management of Data3, 3 (2025), 1–26

    2025

  39. [39]

    Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, et al . 2023. {VBASE}: Unifying online vector similarity search and relational queries via relaxed monotonicity. In17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). 377–395

    2023

  40. [40]

    Andreas Zimmerer, Damien Dam, Jan Kossmann, Juliane Waack, Ismail Oukid, and Andreas Kipf. 2025. Pruning in Snowflake: Working Smarter, Not Harder. In Companion of the 2025 International Conference on Management of Data. 757–770

    2025

  41. [41]

    ZJULearning. 2019. NSG: Navigating Spreading-out Graph For Approximate Nearest Neighbor Search. https://github.com/ZJULearning/nsg. https://doi.org/ 10.14778/3303753.3303754 Accessed: 2026-01-XX. 13

    arXiv 2019