Pith. sign in

REVIEW 5 major objections 5 minor 97 references

Toward Efficient and Scalable Design of In-Memory Graph-Based Vector Search

T0 review · 5 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read A 12-method test at up to 1 billion vectors finds HNSW, Vamana, and ELPIS lead because of incremental insertion plus neighborhood-diversity pruning.

desk verdict Solid experimental survey but the central dominance claim is undercut by implementation asymmetry and the artifact link is a placeholder. read the letter →

arxiv 2509.05750 v1 pith:4TISZYM7 submitted 2025-09-06 cs.IR cs.DBcs.DScs.PF

Ilias Azizi , Karima Echihab , Themis Palpanas , Vassilis Christophides This is my paper · ORCID
classification cs.IRcs.DBcs.DScs.PF
keywords graph-basedvectorsearchapproximatenearestneighborincrementalinsertionneighborhooddiversificationseedselectiondivide-and-conquerbillion-scaleevaluationin-memoryindexing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to settle which algorithmic design choices make in-memory graph-based approximate vector search fast and scalable: it runs 12 state-of-the-art methods on 7 datasets up to 1 billion vectors, isolating five construction paradigms (seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, divide-and-conquer) in a controlled testbed. The central claim is that the best methods use incremental insertion for scalability to 100GB and beyond, and neighborhood diversification for cheap queries, with RND and MOND as the best pruning rules. If correct, new in-memory indexes should be assembled from II+ND plus lightweight hierarchical seeds instead of expensive base-graph pipelines, and divide-and-conquer should be reserved for hard datasets and noisy workloads.

What carries the argument

The carrying object is a five-paradigm taxonomy (seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, divide-and-conquer) used as a controlled testbed: a basic II graph (HNSW's base construction) on which each seed-selection and diversification strategy is swapped in independently. The load-bearing components are the named pruning rules RND (keep a candidate neighbor only if no already-kept neighbor is closer to it), RRND (the same test relaxed by a factor alpha >= 1), and MOND (keep candidates whose edge direction differs from existing neighbors by at least a 60-degree angle), plus seed strategies SN (hierarchical stacked-NSW layers) and KS (k rando

What would settle it

A decisive test would reimplement the top trio (HNSW, Vamana, ELPIS) and the main NP and multi-tree rivals (NSG, SSG, KGraph, SPTAG) from one codebase with uniform engineering and rerun the Deep and Sift 100GB-1B experiments. If a neighborhood-propagation method on a cheaply built base graph matches the II+ND trio, or if equal optimization shifts the billion-scale ranking, the central claim is falsified. A cheaper check: use real million-query streams instead of 100-query extrapolations to see whether the billion-scale preference for hierarchical over k-random seeds holds.

Watch

Extended reading notes

Core claim

The paper establishes that construction paradigm, not the abstract graph family, determines performance. Across 12 methods, only HNSW, Vamana, and ELPIS index and search efficiently at billion scale, and they are precisely the ones that combine incremental insertion (II) with neighborhood diversification (ND). RND and MOND prune best, followed by RRND, while no diversification is worst; and hierarchical stacked-NSW seeds beat k-random sampling at 1B scale. Neighborhood-propagation methods (KGraph, NSG, SSG) fail past 100GB because their expensive base graphs bury them in indexing time and memory.

Load-bearing premise

The evaluation assumes the twelve implementations, after the authors' adjustments, are comparable proxies for the algorithms, so observed differences reflect design paradigm rather than engineering quality; the paper itself concedes full re-implementation is not done, and 100-query workloads are extrapolated to 1M-query behavior.

Editorial extensions

If this is right

  • New in-memory graph indexes should be built with incremental insertion plus RND or MOND pruning; that combination is what indexes and queries past 100GB.
  • At billion scale, seed selection matters: hierarchical stacked-NSW entry points save roughly 10 million distance calculations over k-random sampling at 0.99 recall on Deep1B.
  • For hard datasets (high local intrinsic dimensionality, low contrast) and noisy queries, divide-and-conquer graphs on clustered subsets outperform single-graph beam search.
  • Indexing time is dominated by base-graph construction: ELPIS indexes about 2x faster than HNSW and 2.7x faster than Vamana at billion scale, while SPTAG's multi-tree construction is roughly 24x slower.
  • Because ND and SS cut both wall-clock time and distance computations, the paper argues these design choices double as energy-efficiency levers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The study isolates only seed selection and diversification on a single II+RND base; an equally controlled swap of DC partitioning and NP initialization is a natural next experiment to test causal generality.
  • The billion-scale seed-selection conclusion rests on 100-query extrapolated workloads; a real million-query run with out-of-distribution queries would verify whether the hierarchical-vs-random gap widens.
  • The RND-over-MOND-over-RRND ranking is established for in-memory Euclidean search only; the paper itself notes denser relaxed-alpha graphs help when I/O dominates, so disk-based re-runs map the boundary.
  • Quantifying the actual edge-overlap among RND, RRND, and MOND at billion scale would reveal whether RND's lead is structural or just stricter pruning.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 5 minor

Summary. The paper proposes a taxonomy of five design paradigms for in-memory graph-based approximate nearest neighbor search—seed selection (SS), neighborhood propagation (NP), incremental insertion (II), neighborhood diversification (ND), and divide-and-conquer (DC)—and reports an experimental comparison of twelve public graph-based ANN implementations on seven real and three synthetic datasets up to 1B vectors. The central claims are that II+ND designs (HNSW, VAMANA, ELPIS) dominate in query performance and index efficiency, that NP-based methods with expensive base graphs do not scale, that RND and MOND are the best ND strategies, and that on billion-scale data hierarchical seed selection (SN) becomes preferable to k-random sampling (KS). The paper also proposes research directions and gives implementation-specific recommendations.

Significance. If the claims hold, the paper provides a useful systematization of a fragmented literature and the largest comparative evaluation of graph-based ANN paradigms to date. Strengths include the breadth of datasets (up to 1B vectors), the use of public implementations, controlled cache behavior, a 48-hour indexing limit, repeated runs with trimmed means for query workloads, and release of code. For the ND and SS ablations, the paper reports both wall-clock time and distance calculations, which is the right kind of evidence for isolating algorithmic effects. However, the central paradigm-level conclusions rest on an implementation-comparability assumption that the paper itself concedes is imperfect (Appendix B). Because Figure 21 shows that implementation optimization changes rankings and even scalability, the significance of the headline conclusions is conditional until this confound is addressed.

major comments (5)
  1. [Appendix B, "Implementations" and Figure 21] The paper states: "Ideally, all methods would be re-implemented from scratch to ensure uniformity, but this is highly time-consuming." Yet Section 4 and Conclusions make paradigm-level dominance claims (e.g., "II+ND designs dominate", "NP-based methods do not scale"). Figure 21 demonstrates that optimized ParlayANN versions of Vamana and HNSW are faster than their original counterparts at recall <0.97, and HCNNG Opt scales to 1B whereas the original failed beyond 25GB. This is direct evidence that the observed ranking can be driven by engineering asymmetries rather than by the algorithmic paradigms. The authors should provide a common-codebase control for at least the leading representatives, or explicitly restrict the conclusions to the specific implementations tested, or provide quantitative evidence that engineering differences are second-order (e.g., distance calculations for all SOT
  2. [Section 3.1, "Measures" vs Appendix B, "Comparison"] Section 3.1 says distance calculations are measured for both indexing and query answering, but Appendix B states that search time is reported and that reporting distance calculations is planned future work. The SOTA comparisons in Figures 7 and 16-20 appear to use wall-clock time only. Since the paper's thesis is about algorithmic paradigms rather than engineering quality, wall-clock time conflates the two. Please report distance-calculation curves for the SOTA comparison wherever possible, and clearly label which figures use time and which use distance calculations.
  3. [Section 3.1, "Queries"] Each query workload consists of 100 queries, and the text says "results for 1M queries are extrapolated from these workloads." No statistical procedure is described. All recall-time and recall-distance curves, including the high-recall conclusions in Figures 9 and 10, are based on 100 query points. Please provide confidence intervals or per-query distributions, justify the extrapolation, or relabel the figures as 100-query results. At minimum, the paper should state the uncertainty so that the reported ranking at recall 0.99 is not over-interpreted.
  4. [Appendix A, "DPG" and Section 2.4] Section 2.4 and the taxonomy classify DPG as using MOND. However, Appendix A explicitly says that DPG's publicly available implementation uses RND rather than MOND. Therefore the DPG experiments do not evaluate the MOND strategy attributed to it. The MOND evidence then rests only on the synthetic ND ablation and SSG. Please correct the classification or rerun a MOND-compliant DPG implementation; otherwise the claim that MOND is among the best ND techniques is not fully supported by the SOTA comparison.
  5. [Section 4, Table 1, and Appendix B.3] The paper's treatment of HCNNG is internally inconsistent. Section 4 says "The assessment of HCNNG is based on the optimized parlayANN implementation," while Appendix B.3 reports that HCNNG takes over 24 hours on 25GB and was excluded from larger datasets, and Figure 21 introduces HCNNG Opt separately. The reader cannot tell whether Table 1 and the recommendations in Figure 8 refer to the original or optimized implementation. Please label every HCNNG result with its exact version and discuss both variants consistently.
minor comments (5)
  1. [Appendix B.2] The paragraph beginning "In these experiments, we focus on the four most common SS strategies..." is duplicated verbatim. Please remove the duplicate.
  2. [Section 3.3] The text refers to "Fig.4a" and "Fig.4b" when discussing seed selection, but the seed-selection results appear in Figure 5, while Figure 4 shows ND results. Update the cross-references.
  3. [Sections 2.4, 3.1, Appendix throughout] Several references are given only as "url, 2025" (e.g., the proof in Section 2.4, the artifacts, the supplementary results). These placeholders should be replaced with actual URLs or repository identifiers.
  4. [Figure 8] The caption says "Indexing + 10K queries," but the methodology Section 3.1 specifies 100-query workloads. Clarify the figure's workload size or correct the caption.
  5. [References] The reference "Team, T. P. Parlayann: A deep learning library for parallel computation" appears misattributed; ParlayANN should be cited via Manohar et al. (2024) or the official repository with the correct author list.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation; empirical benchmark with minor self-citation.

full rationale

The paper's central claims — that HNSW, VAMANA, and ELPIS perform best; that incremental-insertion methods scale best; and that RND and MOND are the best diversification techniques — are presented as observed experimental outcomes, not as consequences of a mathematical model fitted to those outcomes. The ND and SS analyses use a controlled II-graph baseline with each strategy implemented independently, so the RND/SN rankings are not true by construction. No parameter is fitted to a subset and then used to predict that same subset; per-method tuning is standard benchmarking practice. The paper does cite its own prior work (Azizi et al. 2023; ELPIS) and evaluates ELPIS, an author-built system, but the conclusions do not rest on the authority of those citations — they rest on wall-clock and distance-calculation measurements. Appendix B's admission that implementations were adjusted rather than re-implemented from scratch is a genuine threat to comparability, and Figure 21 shows implementation quality changes rankings, but that is an experimental-validity caveat, not circular reasoning: the observed numbers are not logically forced by the taxonomy or by self-citation. The 100-query-to-1M extrapolation is an unsupported workload assumption, again not a circular step. Score 1 reflects the presence of self-citations and an author-affiliated system in the evaluation without load-bearing circularity.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claim rests primarily on comparability assumptions rather than on fitted physical or mathematical parameters. The free parameters that matter are the tuning choices (R, L, alpha, theta, per-method construction/search settings) selected by the authors to make each method look its best. The axioms are the comparability of implementations, the adequacy of 100-query workloads, the fairness of timeouts, and the representativeness of the chosen parameter values. No new physical or formal entities are introduced.

free parameters (5)
  • II-baseline graph out-degree R and beam width L = R=60, L=800
    Used to build the incremental-insertion baseline graph on which every ND and SS strategy is tested; chosen by the authors and not varied across datasets (Appendix B.1).
  • RRND relaxation factor alpha = alpha=1.2
    Selected as the best among alpha in [1.2, 2] on Deep/Sift, so the RRND ranking is conditional on a grid-search choice tuned on the same datasets (Appendix B.1).
  • MOND angle threshold theta = theta=60 degrees
    Selected as best among theta in [50, 80] degrees on Deep/Sift; the MOND comparison is conditional on this tuned threshold (Appendix B.1).
  • Per-method construction and search parameters (HNSW M/efConstruction, Vamana alpha and R, ELPIS leaf size/nprobes, etc.) = not stated in the text (deferred to unlinked supplementary)
    Each method is tuned to achieve the best accuracy/efficiency trade-off; the exact grid and selected values are not in the text, so the comparative rankings rest on tuning choices the reader cannot inspect (Appendix B, 'Procedure').
  • Query beam width per method to reach a given recall = not stated per method
    Search comparisons are reported at recall targets such as 0.99 or 0.95, but the beam-width values used to reach those targets are not listed; rankings could shift at other operating points.
assumptions (5)
  • domain assumption The official implementations, after the authors' modifications, are equally optimized proxies for the algorithms they represent.
    Stated in Appendix B 'Implementations'; if false, observed differences reflect engineering quality rather than design paradigms, which is the core comparison the paper makes.
  • domain assumption A 100-query workload extrapolates reliably to 1M-query behavior.
    Section 3.1 'Queries' states that each workload consists of 100 vectors and that results for 1M queries are extrapolated; no statistical justification or error bars are given.
  • domain assumption A 48-hour timeout is a fair scalability criterion for indexing.
    Appendix B 'Procedure'; methods that exceed the timeout are judged non-scalable, which conflates raw implementation speed with algorithmic scalability.
  • ad hoc to paper The hand-picked parameter values (R, L, alpha, theta) are representative of each ND strategy's potential.
    Appendix B.1; these values were grid-searched on the same Deep/Sift datasets, so the ND ranking is conditional on this selection.
  • domain assumption LID and LRC computed on 1M-point samples with k=100 capture dataset difficulty.
    Section 3.1 'Dataset Complexity'; the resulting easy/hard labels drive the claim that DC-based methods excel on hard datasets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Toward Efficient and Scalable Design of In-Memory Graph-Based Vector Search." pith.science (2026). https://pith.science/paper/4TISZYM7

@misc{pith2026250905750,
  author       = {Pith},
  title        = {Pith review of: Toward Efficient and Scalable Design of In-Memory Graph-Based Vector Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4TISZYM7}},
  note         = {Machine review of arXiv:2509.05750}
}
read the original abstract

Vector data is prevalent across business and scientific applications, and its popularity is growing with the proliferation of learned embeddings. Vector data collections often reach billions of vectors with thousands of dimensions, thus, increasing the complexity of their analysis. Vector search is the backbone of many critical analytical tasks, and graph-based methods have become the best choice for analytical tasks that do not require guarantees on the quality of the answers. Although several paradigms (seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, and divide-and-conquer) have been employed to design in-memory graph-based vector search algorithms, a systematic comparison of the key algorithmic advances is still missing. We conduct an exhaustive experimental evaluation of twelve state-of-the-art methods on seven real data collections, with sizes up to 1 billion vectors. We share key insights about the strengths and limitations of these methods; e.g., the best approaches are typically based on incremental insertion and neighborhood diversification, and the choice of the base graph can hurt scalability. Finally, we discuss open research directions, such as the importance of devising more sophisticated data adaptive seed selection and diversification strategies.

Figures

Figures reproduced from arXiv: 2509.05750 by the authors.

Figure 1
Figure 1. Neighborhood diversification approaches influence of one method on another. Within the ND cate￾gory, distinctions are made between different strategies, i.e., No Neighborhood Diversification (NoND), RND, RRND, and MOND (cf. Section 2.4). We identify the SS strategy of each method: KS, KD, SN, MD, LSH, and KM (SF is not used by any SotA method, but we consider it as an alternative strategy). Additionally, some method… view at source ↗
Figure 2
Figure 2. Graph-based ANN indexing paradigms ally adopting a new probabilistic rooting approach. Note that earlier approaches, except from NSW, were mainly NP-based; however, recent studies have focused on devis￾ing methods that leverage the ND, II, and DC paradigms because they lead to superior performance (cf. Section 3). 3. Experimental Evaluation We experimentally evaluate twelve state-of-the-art graph￾based vector search… view at source ↗
Figure 4
Figure 4. Impact of ND choice on query performance (Deep1B) (a) Deep25GB (b) Deep1B [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figures from the paper (9 more)
Figure 3
Figure 3. Figure 3: Dataset complexity Queries. Each query workload consists of 100 vectors processed sequentially to simulate realistic, unpredictable query streams (Palpanas & Beckmann, 2019; Gogolou et al., 2020); results for 1M queries are extrapolated from these workloads. For Deep, …
Figure 6
Figure 6. Figure 6: Indexing time (a) Deep1M (b) Seismic1M (c) Deep1B (d) 10% noise [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 8
Figure 8. Figure 8: Recommendations (Indexing + 10K queries) Recommendations. Our study demonstrates varying perfor￾mance trends across datasets of different sizes, query work￾loads of different hardness and desired recall values. Fig￾ure 8 provides recommendations for methods based on th…
Figure 9
Figure 9. Figure 9: ND methods performance on real-world datasets B.1. Neighborhood Diversification We now evaluate the ND strategies covered in Section 2, i.e., RND, RRND, and MOND against a baseline without ND (NoND). We apply each strategy individually to an II-based graph, where each …
Figure 10
Figure 10. Figure 10: The impact of SS Methods on query answering Deep1M Deep25GB Dist. Calculations (SN) 4.3 billion 1.49 trillion Dist. Calculations (KS) 4.1 billion 1.46 trillion Overhead (SN vs. KS) 182 million 22.3 billion Additional Queries 44,959 1,165,870 [PITH_FULL_IMAGE:figures/…
Figure 12
Figure 12. Figure 12 [PITH_FULL_IMAGE:figures/full_fig_p018_12.png]
Figure 16
Figure 16. Figure 16: Query performance on 1M vectors (a) Deep (b) SALD (c) Seismic (d) Sift (e) RandPow0 (f) RandPow50 [PITH_FULL_IMAGE:figures/full_fig_p019_16.png]
Figure 18
Figure 18. Figure 18: 100GB datasets (a) 1% noise (b) 10% noise [PITH_FULL_IMAGE:figures/full_fig_p019_18.png]
Figure 21
Figure 21. Figure 21: Optimized Implementa￾tions (Deep1B) 19 [PITH_FULL_IMAGE:figures/full_fig_p019_21.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

97 extracted references · 75 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    https://github.com/nmslib/hnswlib, 2019

    Hnswlib - fast approximate nearest neighbor search . https://github.com/nmslib/hnswlib, 2019

    2019

  3. [3]

    https://github.com/scalablesimilaritysearch/ELPIS, 2022

    ELPIS Archive . https://github.com/scalablesimilaritysearch/ELPIS, 2022

    2022

  4. [4]

    https://github.com/iliasazizi/GVS, 2025

    Graph-based vector search: An experimental evaluation of the state-of-the-art (archive). https://github.com/iliasazizi/GVS, 2025

    2025

  5. [5]

    and Ceccarello, M

    Aum \" u ller, M. and Ceccarello, M. The role of local dimensionality measures in benchmarking nearest neighbor search. Inf. Syst., 101: 0 101807, 2021. doi:10.1016/J.IS.2021.101807. URL https://doi.org/10.1016/j.is.2021.101807

    work page arXiv 2021

  6. [6]

    Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms

    Aum \"u ller, M., Bernhardsson, E., and Faithfull, A. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. In International Conference on Similarity Search and Applications, pp.\ 34--49. Springer, 2017

    2017

  7. [7]

    Voronoi diagrams and Delaunay triangulations

    Aurenhammer, F., Klein, R., and Lee, D.-T. Voronoi diagrams and Delaunay triangulations. World Scientific Publishing Company, 2013

    2013

  8. [8]

    Elpis: Graph-based similarity search for scalable data science

    Azizi, I., Echihabi, K., and Palpanas, T. Elpis: Graph-based similarity search for scalable data science. PVLDB , 16 0 (6), 2023

    2023

Show all 97 references
  1. [9]

    Graph-based vector search: An experimental evaluation of the state-of-the-art

    Azizi, I., Echihabi, K., and Palpanas, T. Graph-based vector search: An experimental evaluation of the state-of-the-art. Proceedings of the ACM on Management of Data, 3 0 (1): 0 1--31, 2025

    2025

  2. [10]

    and Lempitsky, V

    Babenko, A. and Lempitsky, V. The Inverted Multi-Index . TPAMI, 37 0 (6), 2015

    2015

  3. [11]

    and Babenko, A

    Baranchuk, D. and Babenko, A. Text-to-image dataset for billion-scale similarity search. https://research.yandex.com/datasets/text-to-image-dataset-for-billion-scale-similarity-search, 2021

    2021

  4. [12]

    Voronet: A scalable object network based on voronoi tessellations

    Beaumont, O., Kermarrec, A.-M., Marchal, L., and Rivi \`e re, \'E . Voronet: A scalable object network based on voronoi tessellations. In 2007 IEEE International Parallel and Distributed Processing Symposium, pp.\ 1--10. IEEE, 2007 a

    2007

  5. [13]

    Peer to peer multidimensional overlays: Approximating complex structures

    Beaumont, O., Kermarrec, A.-M., and Rivi \`e re, \'E . Peer to peer multidimensional overlays: Approximating complex structures. In International Conference On Principles Of Distributed Systems, pp.\ 315--328. Springer, 2007 b

    2007

  6. [14]

    Beis, J. S. and Lowe, D. G. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In Proceedings of IEEE computer society conference on computer vision and pattern recognition, pp.\ 1000--1006. IEEE, 1997

    1997

  7. [15]

    Retrieval-augmented diffusion models

    Blattmann, A., Rombach, R., Oktay, K., M \"u ller, J., and Ommer, B. Retrieval-augmented diffusion models. Advances in Neural Information Processing Systems, 35, 2022

    2022

  8. [16]

    and Palpanas, T

    Boniol, P. and Palpanas, T. Series2Graph: Graph-based Subsequence Anomaly Detection for Time Series . PVLDB , 2020

    2020

  9. [17]

    and von Luxburg, U

    Bubeck, S. and von Luxburg, U. Nearest neighbor clustering: A baseline method for consistent clustering with arbitrary objective functions. JMLR, 10, 2009

    2009

  10. [18]

    Beyond One Billion Time Series: Indexing and Mining Very Large Time Series Collections With i SAX2+

    Camerra, A., Shieh, J., Palpanas, T., Rakthanmanon, T., and Keogh, E. Beyond One Billion Time Series: Indexing and Mining Very Large Time Series Collections With i SAX2+ . Knowledge and information systems, 39 0 (1): 0 123--151, 2014

    2014

  11. [19]

    SPTAG: A library for fast approximate nearest neighbor search, 2018

    Chen, Q., Wang, H., Li, M., Ren, G., Li, S., Zhu, J., Li, J., Liu, C., Zhang, L., and Wang, J. SPTAG: A library for fast approximate nearest neighbor search, 2018. URL https://github.com/Microsoft/SPTAG

    2018

  12. [20]

    Efficient and reliable vector similarity search using asymmetric encoding with nand-flash for many-class few-shot learning

    Chiang, H.-W., Huang, C.-T., Cheng, H.-Y., Tseng, P.-H., Lee, M.-H., and Wu, A.-Y. Efficient and reliable vector similarity search using asymmetric encoding with nand-flash for many-class few-shot learning. In Proceedings of the 30th Asia and South Pacific Design Automation Co...

    2025

  13. [21]

    An overview of end-to-end entity resolution for big data

    Christophides, V., Efthymiou, V., Palpanas, T., Papadakis, G., and Stefanidis, K. An overview of end-to-end entity resolution for big data. ACM Computing Surveys (CSUR), 53 0 (6): 0 1--42, 2020

    2020

  14. [22]

    Diskann: Fast approximate nearest neighbor search on disk

    Croft, D., Gupta, M., Josifovski, V., Narayanan, P., Wu, W., and Xue, Y. Diskann: Fast approximate nearest neighbor search on disk. GitHub repository, 2021. URL https://github.com/microsoft/DiskANN. Accessed: 2024-10-25

    2021

  15. [23]

    and Freund, Y

    Dasgupta, S. and Freund, Y. Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp.\ 537--546, 2008

    2008

  16. [24]

    Nns benchmark: Evaluating approximate nearest neighbor search algorithms in high dimensional euclidean space - dpg algorithm

    DBAIWangGroup. Nns benchmark: Evaluating approximate nearest neighbor search algorithms in high dimensional euclidean space - dpg algorithm. https://github.com/DBAIWangGroup/nns_benchmark/tree/master/algorithms/DPG, 2023. GitHub repository

    2023

  17. [25]

    Desislavov, R. et al. Trends in ai inference energy consumption: Beyond the performance-vs-parameter laws of deep learning. Sustainable Computing: Informatics and Systems, 38, 2023

    2023

  18. [26]

    P., Friedman, S

    Dobkin, D. P., Friedman, S. J., and Supowit, K. J. Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry, 5 0 (4): 0 399--407, 1990

    1990

  19. [27]

    Kgraph, an open source library for k-nn graph construction and nearest neighbor search

    Dong, W. Kgraph, an open source library for k-nn graph construction and nearest neighbor search . www.kgraph.org, 2022

    2022

  20. [28]

    Efficient k-nearest neighbor graph construction for generic similarity measures

    Dong, W., Moses, C., and Li, K. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web, pp.\ 577--586, 2011

    2011

  21. [29]

    Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search

    Echihabi, K., Zoumpatianos, K., Palpanas, T., and Benbrahim, H. Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search . PVLDB , 2019

    2019

  22. [30]

    High-dimensional similarity search for scalable data science

    Echihabi, K., Zoumpatianos, K., and Palpanas, T. High-dimensional similarity search for scalable data science. ICDE, 2021

    2021

  23. [31]

    Hercules Against Data Series Similarity Search

    Echihabi, K., Fatourou, P., Zoumpatianos, K., Palpanas, T., and Benbrahim, H. Hercules Against Data Series Similarity Search . PVLDB , 15 0 (10), 2022

    2022

  24. [32]

    Algorithms in Combinatorial Geometry

    Edelsbrunner, H. Algorithms in Combinatorial Geometry. Springer Publishing Company, Incorporated, 1st edition, 2012. ISBN 3642648738

    2012

  25. [33]

    Engel, A., Monasson, R., and Hartmann, A. K. On large deviation properties of erd \"o s--r \'e nyi random graphs. Journal of Statistical Physics, 117 0 (3): 0 387--426, 2004

    2004

  26. [34]

    Vector approximation based indexing for non-uniform high dimensional data sets

    Ferhatosmanoglu, H., Tuncel, E., Agrawal, D., and El Abbadi, A. Vector approximation based indexing for non-uniform high dimensional data sets. In Proceedings of the ninth international conference on Information and knowledge management, pp.\ 202--209, 2000

    2000

  27. [35]

    for Seismology with Artificial Intelligence, I. R. I. Seismic Data Access . http://ds.iris.edu/data/access/, 2018

    2018

  28. [36]

    Voronoi diagrams and delaunay triangulations

    Fortune, S. Voronoi diagrams and delaunay triangulations. Computing in Euclidean geometry, pp.\ 225--265, 1995

    1995

  29. [37]

    and Cai, D

    Fu, C. and Cai, D. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.07228, 2016

    2016 arXiv

  30. [38]

    Fast approximate nearest neighbor search with the navigating spreading-out graph

    Fu, C., Xiang, C., Wang, C., and Cai, D. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow. , 12 0 (5): 0 461--474, 2019

    2019

  31. [39]

    High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility

    Fu, C., Wang, C., and Cai, D. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021

    2021

  32. [40]

    Gabriel, K. R. and Sokal, R. R. A new statistical approach to geographic variation analysis. Systematic zoology, 18 0 (3): 0 259--278, 1969

    1969

  33. [41]

    Similarity search in high dimensions via hashing

    Gionis, A., Indyk, P., Motwani, R., et al. Similarity search in high dimensions via hashing. In Vldb, volume 99, pp.\ 518--529, 1999

    1999

  34. [42]

    Data Series Progressive Similarity Search with Probabilistic Quality Guarantees

    Gogolou, A., Tsandilas, T., Echihabi, K., Palpanas, T., and Bezerianos, A. Data Series Progressive Similarity Search with Probabilistic Quality Guarantees . In SIGMOD, 2020

    2020

  35. [43]

    On the difficulty of nearest neighbor search

    He, J., Kumar, S., and Chang, S.-F. On the difficulty of nearest neighbor search. arXiv preprint arXiv:1206.6411, 2012

    2012 arXiv

  36. [44]

    Deep residual learning for image recognition

    He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.\ 770--778, 2016

    2016

  37. [45]

    Bore: Energy-efficient banded vector similarity search with optimized range encoding for memory-augmented neural network

    Huang, C.-T., Chang, C.-Y., Cheng, H.-Y., and Wu, A.-Y. Bore: Energy-efficient banded vector similarity search with optimized range encoding for memory-augmented neural network. In 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp.\ 1--6, 2024

    2024

  38. [46]

    Pruned bi-directed k-nearest neighbor graph for proximity search

    Iwasaki, M. Pruned bi-directed k-nearest neighbor graph for proximity search. In International Conference on Similarity Search and Applications, pp.\ 20--33. Springer, 2016

    2016

  39. [47]

    Product quantization for nearest neighbor search

    J \'e gou, H., Douze, M., and Schmid, C. Product quantization for nearest neighbor search. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 33, pp.\ 117--128. IEEE, 2011

    2011

  40. [48]

    Fast and accurate hashing via iterative nearest neighbors expansion

    Jin, Z., Zhang, D., Hu, Y., Lin, S., Cai, D., and He, X. Fast and accurate hashing via iterative nearest neighbors expansion. IEEE transactions on cybernetics, 44 0 (11): 0 2167--2177, 2014

    2014

  41. [49]

    Billion-scale similarity search with GPUs

    Johnson, J., Douze, M., and J \'e gou, H. Billion-scale similarity search with GPUs . IEEE Transactions on Big Data, 7 0 (3): 0 535--547, 2019

    2019

  42. [50]

    Local interpretation of nonlinear regression model with k-nearest neighbors

    Kaneko, H. Local interpretation of nonlinear regression model with k-nearest neighbors. Digital Chemical Engineering, 6: 0 100078, 2023

    2023

  43. [51]

    Dense passage retrieval for open-domain question answering

    Karpukhin, V., O g uz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04906, 2020

    2004 arXiv

  44. [52]

    Kleinberg, J. et al. Small-world phenomena and the dynamics of information. Advances in neural information processing systems, 1: 0 431--438, 2002

    2002

  45. [53]

    Kleinberg, J. M. Navigation in a small world. Nature, 406 0 (6798): 0 845--845, 2000

    2000

  46. [54]

    Approximate nearest neighbor search on high dimensional data: experiments, analyses, and improvement

    Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., and Lin, X. Approximate nearest neighbor search on high dimensional data: experiments, analyses, and improvement . IEEE Transactions on Knowledge and Data Engineering, 32 0 (8): 0 1475--1488, 2019

    2019

  47. [55]

    Hvs: Hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search, 2023

    Lu, K. Hvs: Hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search, 2023. URL https://github.com/Kejing-Lu/hvs

    2023

  48. [56]

    Hvs: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search

    Lu, K., Kudo, M., Xiao, C., and Ishikawa, Y. Hvs: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. Proceedings of the VLDB Endowment, 15 0 (2): 0 246--258, 2021

    2021

  49. [57]

    Malinen, M. I. and Fr \"a nti, P. Balanced k-means for clustering. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, S+ SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings, pp.\ 32--41. Springer, 2014

    2014

  50. [58]

    Approximate nearest neighbor algorithm based on navigable small world graphs

    Malkov, Y., Ponomarenko, A., Logvinov, A., and Krylov, V. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45: 0 61--68, 2014

    2014

  51. [59]

    Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell. , 42 0 (4): 0 824--836, 2020

    2020

  52. [60]

    D., Shen, Z., Blelloch, G., Dhulipala, L., Gu, Y., Simhadri, H

    Manohar, M. D., Shen, Z., Blelloch, G., Dhulipala, L., Gu, Y., Simhadri, H. V., and Sun, Y. Parlayann: Scalable and deterministic parallel graph-based approximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Prac...

    2024

  53. [61]

    Matula, D. W. and Sokal, R. R. Properties of gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical analysis, 12 0 (3): 0 205--222, 1980

    1980

  54. [62]

    and Babenko, A

    Morozov, S. and Babenko, A. Non-metric similarity graphs for maximum inner product search. Advances in Neural Information Processing Systems, 31, 2018

    2018

  55. [63]

    V., Gon c alves, M

    Munoz, J. V., Gon c alves, M. A., Dias, Z., and Torres, R. d. S. Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition, 96: 0 106970, 2019

    2019

  56. [64]

    and Torralba, A

    Oliva, A. and Torralba, A. Modeling the shape of the scene: A holistic representation of the spatial envelope. International journal of computer vision, 42: 0 145--175, 2001

    2001

  57. [65]

    Data series management: The road to big sequence analytics

    Palpanas, T. Data series management: The road to big sequence analytics. ACM SIGMOD Record, 44 0 (2): 0 47--52, 2015

    2015

  58. [66]

    and Beckmann, V

    Palpanas, T. and Beckmann, V. Report on the First and Second Interdisciplinary Time Series Analysis Workshop (ITISA) . ACM SIGMOD Record , 48 0 (3), 2019

    2019

  59. [67]

    I., Nicholson, A

    Petitjean, F., Forestier, G., Webb, G. I., Nicholson, A. E., Chen, Y., and Keogh, E. J. Dynamic time warping averaging of time series allows faster and more accurate classification. In ICDM , 2014

    2014

  60. [68]

    Approximate nearest neighbor search small world approach

    Ponomarenko, A., Malkov, Y., Logvinov, A., and Krylov, V. Approximate nearest neighbor search small world approach. In International Conference on Information and Communication Technologies & Applications, volume 17, 2011

    2011

  61. [69]

    Skip lists: a probabilistic alternative to balanced trees

    Pugh, W. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33 0 (6): 0 668--676, 1990

    1990

  62. [70]

    Reddy, D. R. et al. Speech understanding systems: A summary of results of the five-year research effort. Department of Computer Science. Camegie-Mell University, Pittsburgh, PA, 17: 0 138, 1977

    1977

  63. [71]

    Imagenet large scale visual recognition challenge

    Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115: 0 211--252, 2015

    2015

  64. [72]

    Shamos, M. I. and Hoey, D. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pp.\ 151--162. IEEE, 1975

    1975

  65. [73]

    V., Williams, G., Aum \" u ller, M., Douze, M., Babenko, A., Baranchuk, D., Chen, Q., Hosseini, L., Krishnaswamy, R., Srinivasa, G., Subramanya, S

    Simhadri, H. V., Williams, G., Aum \" u ller, M., Douze, M., Babenko, A., Baranchuk, D., Chen, Q., Hosseini, L., Krishnaswamy, R., Srinivasa, G., Subramanya, S. J., and Wang, J. Results of the neurips'21 challenge on billion-scale approximate nearest neighbor search. CoRR, abs...

    2022 doi arXiv

  66. [74]

    Deep billion-scale indexing

    Skoltech Computer Vision . Deep billion-scale indexing . http://sites.skoltech.ru/compvision/noimi, 2018

    2018

  67. [75]

    Large-scale training system for 100-million classification at alibaba

    Song, L., Pan, P., Zhao, K., Yang, H., Chen, Y., Zhang, Y., Xu, Y., and Jin, R. Large-scale training system for 100-million classification at alibaba. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.\ 2909--2930, 2020

    2020

  68. [76]

    J., Kadekodi, R., Krishaswamy, R., and Simhadri, H

    Subramanya, S. J., Kadekodi, R., Krishaswamy, R., and Simhadri, H. V. Diskann: Fast accurate billion-point nearest neighbor search on a single node. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp.\ 13766--13776, 2019

    2019

  69. [77]

    On approximately searching for similar word embeddings

    Sugawara, K., Kobayashi, H., and Iwasaki, M. On approximately searching for similar word embeddings. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp.\ 2265--2275, 2016

    2016

  70. [78]

    SRS: Solving c-approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index

    Sun, Y., Wang, W., Qin, J., Zhang, Y., and Lin, X. SRS: Solving c-approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index . PVLDB, 8 0 (1), 2014 a

    2014

  71. [79]

    SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index

    Sun, Y., Wang, W., Qin, J., Zhang, Y., and Lin, X. SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index . Proceedings of the VLDB Endowment, 2014 b

    2014

  72. [80]

    Quality and efficiency in high dimensional nearest neighbor search

    Tao, Y., Yi, K., Sheng, C., and Kalnis, P. Quality and efficiency in high dimensional nearest neighbor search. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp.\ 563--576, 2009

    2009

  73. [81]

    Team, T. P. Parlayann: A deep learning library for parallel computation. https://github.com/parlayann/parlayann, 2023. Accessed: 2024-10-25

    2023

  74. [82]

    Datasets for approximate nearest neighbor search

    TEXMEX Research Team . Datasets for approximate nearest neighbor search . http://corpus-texmex.irisa.fr/, 2018

    2018

  75. [83]

    Toussaint, G. T. The relative neighbourhood graph of a finite planar set. Pattern recognition, 12 0 (4): 0 261--268, 1980

    1980

  76. [84]

    Toussaint, G. T. Proximity graphs for nearest neighbor decision rules: recent progress. Interface, 34, 2002

    2002

  77. [85]

    Southwest University Adult Lifespan Dataset (SALD)

    University, S. Southwest University Adult Lifespan Dataset (SALD) . http://fcon_1000.projects.nitrc.org/indi/retro/sald.html?utm_source=newsletter&utm_medium=email&utm_content=See20Data&utm_campaign=indi-1, 2018

    2018

  78. [86]

    Trinary-projection trees for approximate nearest neighbor search

    Wang, J., Wang, N., Jia, Y., Li, J., Zeng, G., Zha, H., and Hua, X.-S. Trinary-projection trees for approximate nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 36 0 (2): 0 388--403, 2013

    2013

  79. [87]

    Wang, J., Huang, P., Zhao, H., Zhang, Z., Zhao, B., and Lee, D. L. Billion-scale commodity embedding for e-commerce recommendation in alibaba. In KDD, 2018

    2018

  80. [88]

    A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search

    Wang, M., Xu, X., Yue, Q., and Wang, Y. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow., 14 0 (11): 0 1964–1978, jul 2021. ISSN 2150-8097. doi:10.14778/3476249.3476255. URL https://doi.org/10.14778/347624...

    1964

  81. [89]

    LeaFi: Data Series Indexes on Steroids with Learned Filters

    Wang, Q., Ileana, I., and Palpanas, T. LeaFi: Data Series Indexes on Steroids with Learned Filters . Proc. ACM Manag. Data , 2025

    2025

  82. [90]

    Watts, D. J. and Strogatz, S. H. Collective dynamics of ‘small-world’networks. nature, 393 0 (6684): 0 440--442, 1998

    1998

  83. [91]

    A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces

    Weber, R., Schek, H.-J., and Blott, S. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces . In Proc. VLDB, pp.\ 194--205, 1998

    1998

  84. [92]

    C., and Giles , C

    Williams , K., Li , L., Khabsa , M., Wu , J., Shih , P. C., and Giles , C. L. A web service for scholarly big data information extraction. In ICWS, 2014

    2014

  85. [93]

    Ngt: Neighborhood graph and tree for high-dimensional data

    Yahoo Japan Corporation . Ngt: Neighborhood graph and tree for high-dimensional data. https://github.com/yahoojapan/NGT, 2022. Accessed: 2024-10-20

    2022

  86. [94]

    Yianilos, P. N. Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda, volume 93, pp.\ 311--21, 1993

    1993

  87. [95]

    Fast knn graph construction with locality sensitive hashing

    Zhang, Y.-M., Huang, K., Geng, G., and Liu, C.-L. Fast knn graph construction with locality sensitive hashing. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp.\ 660--674. Springer, 2013

    2013

  88. [96]

    Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces

    Zhao, X., Tian, Y., Huang, K., Zheng, B., and Zhou, X. Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces. Proceedings of the VLDB Endowment, 16 0 (8): 0 1979--1991, 2023

    1979

  89. [97]

    Generating data series query workloads

    Zoumpatianos, K., Lou, Y., Ileana, I., Palpanas, T., and Gehrke, J. Generating data series query workloads. The VLDB Journal, 27 0 (6): 0 823--846, December 2018. ISSN 1066-8888. doi:10.1007/s00778-018-0513-x. URL https://doi.org/10.1007/s00778-018-0513-x

    2018 doi

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.