Pith. sign in

REVIEW 3 major objections 7 minor 3 cited by

PiPNN claims graph-based ANN indexes can be built up to 12.9x faster by replacing beam-search candidate selection with an LSH-based online prune, at equal query quality.

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 22:53 UTC pith:M4WGKBUU

load-bearing objection A serious partition-then-prune construction for graph ANNS with a genuinely new online pruning kernel; the speedups are plausible but need code and variance statistics to be fully convincing. the 3 major comments →

arxiv 2602.21247 v3 pith:M4WGKBUU submitted 2026-02-17 cs.DB cs.DCcs.IR

PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

Tobias Rubel , Richard Wen , Laxman Dhulipala , Lars Gottesb\"uren , Rajesh Jayaram , Jakub {\L}\k{a}cki This is my paper
classification cs.DB cs.DCcs.IR
keywords approximate nearest neighbor searchgraph-based indexingLSH pruninghistory-independent pruningrandomized ball carvingparallel index constructionbillion-scale datasetsk-NN graph construction
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 claims that the search bottleneck that makes graph-based ANN indexes slow to build is not necessary: candidate neighbor selection can be replaced by an overlapping partition of the dataset plus a history-independent online prune. The authors introduce PiPNN, which carves points into small overlapping leaves with randomized ball carving, computes all-pairs distances inside each leaf with dense matrix multiplication, and feeds a small set of bi-directed k-NN edges per point into HashPrune, an LSH-based pruning rule that keeps the nearest candidate per angular bucket under a bounded reservoir. They show experimentally that PiPNN matches the query quality of HNSW and Vamana while building indexes up to 11.6x and 12.9x faster respectively, and that a high-quality billion-scale index can be built in under 20 minutes on a single multicore machine. If correct, this removes the main obstacle to using graph indexes in applications that rebuild or retune indexes frequently, and turns index construction into a throughput-oriented, GEMM-bound workload.

Core claim

On the paper's own terms: PiPNN's thesis is that the classic two-stage recipe for graph-based ANNS — find candidates by beam-searching a partial index, then prune for directional diversity — can be inverted. Instead of searching, PiPNN generates overlapping leaves by randomized ball carving so that nearby points co-locate with high probability, and within each leaf computes all pairwise distances with GEMM kernels, then passes only a sparse set of bi-directed k-NN edges to HashPrune. HashPrune is the load-bearing piece: it hashes the residual vector c-p with a small set of random hyperplanes and keeps the closest candidate per hash bucket in a fixed-size reservoir, evicting the farthest when

What carries the argument

HashPrune: an online, history-independent pruning rule — LSH-hashed residuals into m random hyperplanes, reservoir of ℓ_max nearest-per-bucket candidates, evicting global furthest on overflow. It is what lets PiPNN stream candidate edges from overlapping ball-carved leaves in arbitrary order while keeping memory bounded and graph quality comparable to RNG-based prunes. The other elements — Randomized Ball Carving with multi-level fanout for overlap, leaf k-NN graphs with GEMM distance matrices — exist to feed HashPrune the right candidate sets.

Load-bearing premise

The overlapping partition produced by randomized ball carving must place each point's true nearest neighbors (and enough long-range edges for navigability) inside at least one shared leaf with high enough probability — an unproven, data-dependent assumption; if near neighbors are routinely split across leaves, HashPrune never sees the right candidate edges and recall collapses.

What would settle it

Take a dataset engineered so that for each point, its k nearest neighbors lie mostly outside all of the leaves it is assigned to (e.g., a mixture of tight high-dimensional clusters with leaders sampled from other clusters so that near-neighbor relations cross leaf boundaries), then run PiPNN with default parameters; if recall at 0.9 cannot be reached without a large increase in fanout or replicas, the partition assumption is the bottleneck.

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

If this is right

  • Index construction for graph-based ANNS ceases to be search-bound: builds 4–12.9x faster than HNSW/Vamana with equal query recall (up to 11.6x vs Vamana and 12.9x vs HNSW).
  • Billion-scale high-quality indexes become a <20-minute single-machine job (first time reported).
  • Approximate k-NN graph construction (95% recall, k=10) is 1.4–6.9x faster end-to-end than Vamana/HNSW because build time dominates.
  • Memory during construction is bounded by reservoir size (64–128 per point), enabling higher quality without extra intermediate memory.
  • Extra replication can match 2-pass Vamana quality without the degree inflation that HCNNG suffers.
  • The final RobustPrune step adds only ~10% build time while improving QPS by about 10% at high recall.

Where Pith is reading between the lines

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

  • The history-independence of HashPrune suggests the same online prune could be dropped into other edge-streaming pipelines (e.g., distributed graph building, dynamic insertion, graph-of-graphs) wherever candidates arrive in arbitrary order with a bounded adjacency budget.
  • Since PiPNN's cost is dominated by GEMM, the paper's own suggested next steps — quantized GEMM and GPU/TPU offload — could push build times further; an editorial extrapolation is that construction scale may soon be bounded by memory bandwidth rather than search latency.
  • The partition assumption is data-dependent; a testable extension is to adapt fanout/leader counts per local density or to hybridize with a small amount of search for points whose leaves fail to produce enough non-colliding candidates.
  • The reported speedups hold for the degree-64, recall-oriented regime; one could test whether the advantage persists for very low-degree graphs or for metric spaces where the hyperplane hash's angular assumption is weak, such as inner-product/MIPS on non-normalized vectors.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 7 minor

Summary. The paper proposes PiPNN, a graph-based ANNS index construction method that replaces incremental beam-search-based candidate selection with a pipeline of three stages: overlapping partitioning via Randomized Ball Carving (RBC), within-leaf k-NN candidate generation using dense GEMM distance computations, and an online LSH-based pruning rule (HashPrune) that maintains bounded-degree adjacency lists. An optional final RobustPrune is applied. The central empirical claim is that PiPNN builds graphs of quality comparable to HNSW/Vamana while being up to 11.6x and 12.9x faster respectively at build time (average 6.32x and 10.4x), and that it builds billion-scale indexes in under 20 minutes on a single multicore machine. The paper reports extensive experiments on four billion-scale datasets, a 35M high-dimensional dataset, and 100M-scale ablations, including comparisons to HCNNG, MIRAGE, FastKCNA, and k-NN graph construction as a downstream task.

Significance. If the main claims hold, PiPNN is a significant practical contribution: it demonstrates that a carefully engineered partition-then-prune pipeline can match the query quality of incremental graph methods while avoiding the random-access 'search bottleneck', and HashPrune is a simple, order-independent, memory-bounded pruning primitive that is likely to be reused. The paper is also unusually careful in its ablation work: it evaluates four partitioning methods, five leaf-building/prune kernels, fanout vs. replication, hash resolution, and final-prune impact. It is transparent about modifications to MIRAGE and about memory limitations preventing billion-scale runs of MIRAGE/FastKCNA. However, the central quality claim is supported only empirically on the evaluated datasets; there is no theoretical or synthetic-data guarantee that RBC co-locates true nearest neighbors with enough probability, and the experimental section lacks error bars, repeated-run statistics, and a released artifact. The contribution is therefore promising and likely useful, but the load-bearing co-location assumption needs strengthening before the claims can be regarded as fully established.

major comments (3)
  1. [Sec. 4.1, Alg. 5; Sec. 4.2, Alg. 3] The central quality claim depends on an unproven, data-dependent co-location assumption. HashPrune is a filter: for a point p, it can only retain candidate edges that appear in a leaf shared with p. Under the fanout/multi-level fanout scheme, a point is sent at each recursion level only to its local_fanout nearest leaders (Alg. 5, lines 6-9). If a true nearest-neighbor pair is separated at a level because they are assigned to different leader Voronoi cells, the pair will not be offered to HashPrune at any descendant leaf. The paper provides empirical ablations on BigANN, SPACEV, OpenAI, and WikiCohere (Sec. 5.1, Figs. 7-8), but these are favorable, relatively well-clustered benchmarks. No worst-case, distributional, or even synthetic stress test is given, and the determinism proof (A.8) does not address co-location. This is load-bearing: if RBC splits true NN pairs on a different data di
  2. [Sec. 5, Fig. 5; Appendix A.9] The experimental evidence is extensive but lacks statistical reproducibility. All speedup and QPS-recall comparisons appear to be single runs; no standard deviations, bootstrapped confidence intervals, or repeated seeds are reported for the main results in Fig. 5. This matters because build-time speedups of 4-12x are the headline claim, and build time can be affected by OS jitter, scheduling, and memory placement on multi-socket machines. Additionally, the MIRAGE baseline had to be modified to use 64-bit integer indices (A.9), and MIRAGE could not run on billion-scale datasets; the modifying change is acknowledged as potentially impacting performance. I recommend the authors release the artifact with exact commands, hyperparameters, and seeds, and report at least 3-5 runs for the key construction-time comparisons and for the quality-vs-QPS curves.
  3. [A.7, A.8] The theoretical analysis is not at the level needed to support the central algorithmic claims. The asymptotic bound in A.7 assumes that randomized ball carving 'divides points across subproblems roughly evenly in expectation' and states a high-probability recursion depth, but no formal concentration argument is provided for the fanout variant. More importantly, the expected-time formula does not quantify the probability that a given point and its true kNN are co-located in a leaf, which is the property that makes HashPrune's candidate stream meaningful. The determinism proof in A.8 is correct in spirit but the proof sketch for Lemma A.2 only shows the final reservoir contains the nearest non-colliding candidates; it does not address the case where the globally farthest eviction interacts with colliding candidates in a way that might depend on insertion order. I believe the proof can be f
minor comments (7)
  1. [Alg. 3, line 11] In Algorithm 3, the eviction comparison 'if ∥p,c∥<z' compares a distance to a point, not to a distance; it should be 'if ∥p,c∥<∥p,z∥'.
  2. [Alg. 2, line 2] In Algorithm 2, the argmin should be over the candidate set N, not the whole point set X: 'argmin_{y∈N} ∥x,y∥'.
  3. [Alg. 1, line 5] Algorithm 1 uses the undefined variable 'curr' in 'Neighbors(curr)'; this should be 'p' (the current nearest unvisited point).
  4. [Theorem 3.1] The text 'See Supplement A.2 for a detailed proof' is incorrect: the HashPrune proof is in Appendix A.8, while A.2 is about fanout vs. replication.
  5. [Sec. 5.1, Multi-Level Fanout] The reference to 'Supplement A.2' for a more detailed explanation of multi-level fanout should point to A.1.4, which contains that explanation; A.2 is the formal cost comparison.
  6. [Alg. 5, line 3] The leader sampling uses P_samp·|P|, but if P_samp is a fraction and the subproblem is small, this can be less than 1; the pseudocode does not specify a minimum number of leaders. This is worth clarifying.
  7. [Fig. 2] The caption says 'Shading represents the probability of collision based on number of bits used', but the figure is static and the probability is not actually visible in the shading; a short probability expression or legend would help.

Circularity Check

0 steps flagged

No significant circularity; central derivation is independent, with only a minor non-load-bearing self-citation.

full rationale

The paper's claimed derivation chain is not circular. HashPrune's only analytical premise is the classical LSH collision estimate P[hp(c)=hp(c')]=(1-theta/pi)^m, credited to Charikar [12], an external result; the history-independence guarantee is proved in the paper itself (Appendix A.8, Lemma A.2) rather than assumed. The partitioning scheme (RBC) is selected by comparative ablation (Sec. 5.1, Appendix A.1), not derived from a fitted parameter, and no quantity later reported as a prediction is used to define the algorithm. The speed and quality claims are direct benchmark measurements against external implementations (HNSW, Vamana, MIRAGE, FastKCNA). The only self-citations (e.g., [18] in Appendix A.1.3 for Sorting-LSH, and [28] for baseline implementations) are non-load-bearing: they support an ablation alternative and baseline code, not the central claim. The unproven co-location assumption for RBC is a correctness risk, not a circularity, because the paper does not define query quality in terms of that assumption. Score 2 reflects the mild self-reference in the appendix, not a reduction of the central result to its own inputs.

Axiom & Free-Parameter Ledger

9 free parameters · 3 axioms · 0 invented entities

PiPNN rests on many tunable hyperparameters (leaf size, fanout, hash bits, reservoir size, replication count, leaf k) that are set by the authors through ablations on the same datasets used in the final SOTA comparison. It also depends on two data-distribution assumptions: balanced ball carving for the time analysis, and co-location of true neighbors for the quality analysis. No new physical entities are postulated; HashPrune is an algorithmic data structure, not an invented entity in the 'graviton' sense.

free parameters (9)
  • leaf k-NN parameter k = 2 (3-4 also viable)
    Chosen via ablation on MS-SPACEV (Fig 11); controls leaf candidate density and downstream graph degree.
  • HashPrune hash bits m = 12
    Swept over 6-16 on SPACEV-100M; 6 degrades quality and 8-16 are all acceptable (Supplement Fig 13).
  • maximum leaf size C_max = 1024-2048
    User-tunable cache-size bound stated in Sec 4.1; affects GEMM tile size and candidate quality.
  • minimum leaf size C_min = not specified
    Used in Algorithm 5 to merge undersized clusters; value never reported, so the exact partition behavior is under-specified.
  • leader fraction P_samp = not specified
    Fraction of points sampled as leaders in randomized ball carving; controls recursion arity and is part of the hyperparameter set.
  • multi-level fanout schedule = e.g., 10 at top level, 3 at second level
    Selected by experimentation (Sec 4.1, Fig 3); replaces replication to create overlapping partitions.
  • HashPrune reservoir size l_max = 64, 128, 192 tested
    Intermediate reservoir cap; final graph degree capped at 64, but the default intermediate reservoir size is not explicitly fixed in the text (Table 5).
  • number of replicas = 1 or 2
    Replication trades build time for quality; 2-replica PiPNN is claimed to match 2-pass Vamana.
  • RobustPrune alpha = not stated
    Final pruning reuses Vamana's RobustPrune with real-valued alpha; the exact value used in PiPNN is not reported.
axioms (3)
  • standard math Random hyperplane LSH collision probability P[h_p(c)=h_p(c')]=(1-theta/pi)^m
    Invoked in Sec 3 'Why HashPrune Works' to justify directional diversity via angular cones; follows from Charikar's classical LSH analysis [12].
  • domain assumption Randomized Ball Carving divides points roughly evenly in expectation and recursion depth is O(log_l n) with high probability
    Explicitly stated as 'reasonable in practice' in Appendix A.7 and used for the running-time analysis; it can fail on adversarial or skewed point distributions.
  • domain assumption Nearby points co-locate in at least one leaf with sufficiently high probability under RBC plus fanout
    This is the load-bearing data-distribution assumption for index quality: if true nearest neighbors are split across leaves, HashPrune never receives the right candidates. Only empirical ablations are given, not a distributional or worst-case guarantee.

pith-pipeline@v1.3.0-alltime-deepseek · 23425 in / 12748 out tokens · 141329 ms · 2026-08-02T22:53:04.888420+00:00 · methodology

0 comments
read the original abstract

The fastest indexes for Approximate Nearest Neighbor Search today are also the slowest to build: graph-based methods like HNSW and Vamana achieve state-of-the-art query performance but have large construction times due to relying on random-access-heavy beam searches. We introduce PiPNN (Pick-in-Partitions Nearest Neighbors), an ultra-scalable graph construction algorithm that avoids this ``search bottleneck'' that existing graph-based methods suffer from. PiPNN's core innovation is HashPrune, a novel online pruning algorithm which dynamically maintains sparse collections of edges. HashPrune enables PiPNN to partition the dataset into overlapping sub-problems, efficiently perform bulk distance comparisons via dense matrix multiplication kernels, and stream a subset of the edges into HashPrune. HashPrune guarantees bounded memory during index construction which permits PiPNN to build higher quality indices without the use of extra intermediate memory. PiPNN builds state-of-the-art indexes up to 11.6x faster than Vamana (DiskANN) and up to 12.9x faster than HNSW. PiPNN is significantly more scalable than recent algorithms for fast graph construction. PiPNN builds indexes at least 19.1x faster than MIRAGE and 17.3x than FastKCNA while producing indexes that achieve higher query throughput. PiPNN enables us to build, for the first time, high-quality ANN indexes on billion-scale datasets in under 20 minutes using a single multicore machine.

Figures

Figures reproduced from arXiv: 2602.21247 by Jakub {\L}\k{a}cki, Lars Gottesb\"uren, Laxman Dhulipala, Rajesh Jayaram, Richard Wen, Tobias Rubel.

Figure 1
Figure 1. Figure 1: Build time speedup compared to HNSW on six bench￾marks, including billion-scale inputs from big-ann-benchmarks. Due to the notorious difficulty of finding the exact nearest neigh￾bors in high-dimensional spaces [10] and the fact that real-world ap￾plications typically tolerate small errors, modern embedding-based applications leverage approximate nearest-neighbor search (ANNS). In recent years, graph-based… view at source ↗
Figure 2
Figure 2. Figure 2: Impact of resolution on neighbor retention. Shading represents the probability of collision based on number of bits used in the HashPrune hash (𝑚). (a) At coarse resolution, 𝑐 ′ collides with and evicts the farther neighbor𝑐2. (b) At finer resolution, both edges are retained. For each point 𝑝, we generate an individualized hash function ℎ𝑝 , which takes a candidate point 𝑐 and hashes the residual of 𝑝 and … view at source ↗
Figure 4
Figure 4. Figure 4: Portion of time spent in Partitioning, Leaf Building, and Final Prune for the four ablation datasets. performing a prune on the final HashPrune reservoirs (Final Prune). We show the percentage of time taken by each phase in [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: QPS vs recall for all algorithms on four billion-size datasets (BigANN-1B, MS-SPACEV-1B, MS-TURING-1B, and DEEP-1B) and two high-dimensional datasets (OpenAIArXiv-2M and WikipediaCohere-35M). Build times are listed in the legends in seconds. PiPNN) are always built faster than 1-pass Vamana, while always being superior in quality (typically equivalent to 2-pass Vamana). Index Construction Times. On the ver… view at source ↗
Figure 6
Figure 6. Figure 6: shows the results of our 𝑘-NN construction, showing the overall slowdown of each method over PiPNN, which is always the BigANN-100M SPACEV-100M Deep-100M Turing-100M OpenAI 0 2 4 6 Slowdown (relative to fastest) k-NN Building Algorithm hnswlib Vamana PiPNN [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 8
Figure 8. Figure 8: Given equal point repeat budget, all three methods exhibit similar QPS at fixed recall. 10 20 30 40 50 60 Combined Fanout (num clusters * fanout) 0 1000 2000 Aggregate Bucket Time (s) SpaceV 10 20 30 40 50 60 Combined Fanout (num clusters * fanout) 0 50 100 Aggregate Bucket Time (s) OpenAI 10 20 30 40 50 60 Combined Fanout (num clusters * fanout) 0 1000 2000 Aggregate Bucket Time (s) BigANN 10 20 30 40 50 … view at source ↗
Figure 9
Figure 9. Figure 9: Given equal point repeat budget, Multi-level Fanout greatly reduces time to partition into leaves (termed ‘Buckets’ here). of the high number of leaders selected in each subproblem. Thus, reducing the cost of the top 2 levels of recursion has a very large impact on overall partitioning time. This also limits how many levels we can distribute fanout across, as any fanout beyond the second level has a high l… view at source ↗
Figure 11
Figure 11. Figure 11: Varying the parameter 𝑘 for 𝑘-NN graphs in leaves. bigann openai spacev wiki Dataset 0 10 20 30 40 50 60 Normalized Build Time (Slowdown Factor) Normalized Build Leaf Time Comparison Methods All-to-All Prune All-to-All Prune (D) All-to-All Prune (D,E) All-to-All Prune (D,E,VQ) KNN KNN (D) KNN (D,E) KNN (D,E,VQ) [PITH_FULL_IMAGE:figures/full_fig_p014_11.png] view at source ↗
Figure 10
Figure 10. Figure 10: Comparing QPS-recall trade-offs of leaf pruning meth￾ods. Bi-directed 𝑘-NN (𝑘-NN) performs best. indexes that require fewer visited nodes at high recall, but the in￾creased number of comparisons when visiting a node outweighs the benefit. RobustPrune in the leaves produces candidate lists that are unlikely to be further sparsified by either HashPrune or the final ap￾plication of RobustPrune. Thus RobustPr… view at source ↗
Figure 13
Figure 13. Figure 13: Parameter sweep over hash-family sizes in the range of [6, 16] on SPACEV (100M) dataset, without any final prune. All values between 8 and 16 are suitable. procedure not only enables better scalability, but it also avoids dynamically resizing the intermediate candidate lists. To test whether limiting the candidates during construction impacts query performance, we compared reservoir sizes of 64, 128, and … view at source ↗
Figure 14
Figure 14. Figure 14: shows results for the methods able to run the billion￾scale Text2Image dataset [37] comprised of 200-dimensional float vectors outfitted with the MIPS dissimilarity measure. HNSW is not displayed due to being unable to achieve 0.8 recall. PiPNN performs better than other methods with respect to maximum achieved recall. 0.85 0.90 0.95 1.00 Recall 105 106 QPS Text2Image-1B hcnng (19094 s) pipnn-1 (1471 s) p… view at source ↗
Figure 15
Figure 15. Figure 15: Results for the 100M sized ablation datasets MS-SPACEV￾100M and BigANN-100M comparing PiPNN against new recent methods for scaleable index build. input points. Within each level, up to 𝑓 𝑛 instances of points each undergo 𝑑-dimensional distance computations with the ℓ leaders in its subproblem (where 𝑓 is the amount of fanout performed at the prior level of recursion). It follows that partitioning takes 𝑂… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. QuIVer: Rethinking ANN Graph Topology via Training-Free Binary Quantization

    cs.DB 2026-05 unverdicted novelty 7.0

    QuIVer constructs ANN graph indices entirely inside a 2-bit quantized metric space, delivering high recall and throughput on embedding datasets while using far less memory than standard HNSW implementations.

  2. QuIVer: Rethinking ANN Graph Topology via Training-Free Binary Quantization

    cs.DB 2026-05 unverdicted novelty 7.0

    QuIVer performs Vamana-style graph construction entirely inside a 2-bit Sign-Magnitude BQ space, achieving >=88% Recall@10 on contrastive-learning embeddings and 2.5-5.5x higher throughput than DiskANN/HNSW at matched...

  3. QuIVer: Rethinking ANN Graph Topology via Training-Free Binary Quantization

    cs.DB 2026-05 unverdicted novelty 6.0

    QuIVer constructs ANN graphs using only 2-bit sign-magnitude binary quantization for topology decisions, achieving at least 88% Recall@10 at high throughput with low memory on embedding datasets.

Reference graph

Works this paper leans on

50 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    Razenshteyn, and Ludwig Schmidt

    Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Distance. 1225–1233

    2015

  2. [2]

    Alexandr Andoni and Hengjie Zhang. 2023. Sub-quadratic (1+𝜖)-approximate Euclidean Spanners, with Applications. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 98–112

    2023

  3. [3]

    Sunil Arya and David M Mount. 1993. Approximate nearest neighbor queries in fixed dimensions.. InSODA, Vol. 93. Citeseer, 271–280

    1993

  4. [4]

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

    2020

  5. [5]

    Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Łącki, Vahab Mirrokni, and Peilin Zhong. 2025. Massively parallel minimum spanning tree in general metric spaces. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 143–174

    2025

  6. [6]

    Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. InProceedings of the IEEE conference on computer vision and pattern recognition. 2055–2063

    2016

  7. [7]

    Yair Bartal, Moses Charikar, and Danny Raz. 2001. Approximating min-sum k-clustering in metric spaces. InProceedings of the thirty-third annual ACM symposium on Theory of computing. 11–20

    2001

  8. [8]

    MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Moham- madTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni

  9. [9]

    Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, and Erik Waingarten

  10. [10]

    Kakade, and John Langford

    Alina Beygelzimer, Sham M. Kakade, and John Langford. 2006. Cover trees for nearest neighbor(ACM International Conference Proceeding Series), Vol. 148. ACM, 97–104

    2006

  11. [11]

    CJ Carey, Jonathan Halcrow, Rajesh Jayaram, Vahab Mirrokni, Warren Schudy, and Peilin Zhong. 2022. Stars: Tera-Scale Graph Building for Clustering and Learning.Advances in Neural Information Processing Systems35 (2022), 21470– 21481

    2022

  12. [12]

    Moses Charikar. 2002. Similarity estimation techniques from rounding algo- rithms. InProceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada. ACM, 380–388

    2002

  13. [13]

    Laxman Dhulipala, David Eisenstat, Jakub Łącki, Vahab Mirrokni, and Jessica Shi. 2021. Hierarchical agglomerative graph clustering in nearly-linear time. In International conference on machine learning. PMLR, 2676–2686

    2021

  14. [14]

    Laxman Dhulipala, Jakub Łącki, Jason Lee, and Vahab Mirrokni. 2023. Terahac: Hierarchical agglomerative clustering of trillion-edge graphs.Proceedings of the ACM on Management of Data1, 3 (2023), 1–27

    2023

  15. [15]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph.Proceedings of the VLDB Endowment12, 5 (2019), 461–474. https://doi.org/10.14778/3303753. 3303754

    work page doi:10.14778/3303753 2019

  16. [16]

    Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yixin Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. 2023. Retrieval-augmented generation for large language models: A survey.arXiv preprint arXiv:2312.10997 2, 1 (2023)

    Pith/arXiv arXiv 2023

  17. [17]

    Google. 2026. Highway: Performance-portable SIMD. https://github.com/ google/highway

    2026

  18. [18]

    Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram, and Jakub Lacki. 2025. Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search.Proc. VLDB Endow.18, 6 (2025), 1649–1662

    2025

  19. [19]

    Yang Gu, Caroline Zhou, Qiao Zhang, Scott Wang, Yongzhe Wang, Li Zhang, Nikos Parotsidis, Cj Carey, Ashkan Fard, Mingyan Gao, et al. 2025. Streaming Trends: A Low-Latency Platform for Dynamic Video Grouping and Trending Cor- pora Building. InProceedings of the Nineteenth ACM Conference on Recommender Systems. 1091–1094

    2025

  20. [20]

    Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org

    2010

  21. [21]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613

    1998

  22. [22]

    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

  23. [23]

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

    2011

  24. [24]

    Ravishankar Krishnaswamy, Magdalen Dobson Manohar, and Harsha Vardhan Simhadri. 2024. The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search.IEEE Data Eng. Bull.(2024)

    2024

  25. [25]

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rock- täschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks.Advances in Neural Information Processing Systems33 (2020), 9459–9474

    2020

  26. [26]

    Yuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan

  27. [27]

    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

  28. [28]

    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 algo- rithms. InProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 270–285

    2024

  29. [29]

    Bhaskar Mitra, Nick Craswell, et al. 2018. An introduction to neural information retrieval.Foundations and Trends®in Information Retrieval13, 1 (2018), 1–126

    2018

  30. [30]

    Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres

  31. [31]

    Arvind Neelakantan, Tao Xu, Raul Puri, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris Hallacy, et al

  32. [32]

    Ninh Pham and Tao Liu. 2022. Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search.CoRRabs/2206.01382 (2022). https: //doi.org/10.48550/arXiv.2206.01382 arXiv:2206.01382

    Pith/arXiv arXiv doi:10.48550/arxiv.2206.01382 2022

  33. [33]

    Nils Reimers. 2022. Cohere/wikipedia-22-12-en-embeddings. https://huggingface. co/datasets/Cohere/wikipedia-22-12-en-embeddings

    2022

  34. [34]

    Deepjyoti Roy and Mala Dutta. 2022. A systematic review and research perspec- tive on recommender systems.Journal of Big Data9, 1 (2022), 59

    2022

  35. [35]

    Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Łăcki, and Vahab Mir- rokni. 2021. Scalable community detection via parallel correlation clustering. Proceedings of the VLDB Endowment14, 11 (2021), 2305–2313

    2021

  36. [36]

    Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. 2024. Results of the Big ANN: NeurIPS’23 compe- tition.arXiv preprint arXiv:2409.17424(2024). Tobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram, and Jakub Łącki

    Pith/arXiv arXiv 2024

  37. [37]

    Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krish- naswamny, Gopal Srinivasa, et al. 2022. Results of the NeurIPS’21 challenge on billion-scale approximate nearest neighbor search. InNeurIPS 2021 Competitions and Demonstrations Track. PMLR, 177–189

    2022

  38. [38]

    Jack Spalding-Jamieson, Eliot Wong Robson, and Da Wei Zheng. 2025. Scalable k- Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search. arXiv preprint arXiv:2502.06163(2025)

    Pith/arXiv arXiv 2025

  39. [39]

    Tamer Özsu

    Sairaj Voruganti and M. Tamer Özsu. 2025. MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search.Proc. ACM Manag. Data3, 3, Article 188 (June 2025), 27 pages. https://doi.org/10.1145/ 3725325

    2025

  40. [40]

    Bennett, Junaid Ahmed, and Arnold Overwijk

    Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021. Approximate Nearest Neighbor Neg- ative Contrastive Learning for Dense Text Retrieval. InInternational Conference on Learning Representations, ICLR

    2021

  41. [41]

    Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. 2024. Revisiting the index construction of proximity graph-based approximate nearest neighbor search.arXiv preprint arXiv:2410.01231(2024)

    Pith/arXiv arXiv 2024

  42. [42]

    Shangdi Yu, Laxman Dhulipala, Jakub Łącki, and Nikos Parotsidis. 2025. Dyn- HAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering. In Proceedings of the 2025 SIAM International Conference on Data Mining (SDM). SIAM, 252–260

    2025

  43. [43]

    Shangdi Yu, Joshua Engels, Yihao Huang, and Julian Shun. 2025. Pecann: Paral- lel efficient clustering with graph-based approximate nearest neighbor search. In2025 Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA). SIAM, 1–17

    2025

  44. [44]

    Alexandros Zeakis, George Papadakis, Dimitrios Skoutas, and Manolis Koubarakis. 2023. Pre-Trained Embeddings for Entity Resolution: An Experi- mental Analysis.Proc. VLDB Endow.16, 9 (2023), 2225–2238

    2023

  45. [45]

    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.Proceedings of the VLDB Endowment16, 8 (2023), 1979–1991. PiPNN : A Framework for Ultra-Scalable Graph-Based Nearest Neighbor Indexing A APPENDIX A.1 Partitioning Methods In this sect...

    2023

  46. [2017]

    Affinity clustering: Hierarchical clustering at scale.Advances in Neural Information Processing Systems30 (2017)

    2017

  47. [2019]

    Hierarchical clustering-based graphs for large scale approximate nearest neighbor search.Pattern Recognition96 (2019), 106970

    2019

  48. [2020]

    VLDB Endow.14, 1 (2020), 50–60

    Deep entity matching with pre-trained language models.Proc. VLDB Endow.14, 1 (2020), 50–60

    2020

  49. [2022]

    Text and code embeddings by contrastive pre-training.arXiv preprint arXiv:2201.10005(2022)

    Pith/arXiv arXiv 2022

  50. [2025]

    Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair.arXiv preprint arXiv:2508.06774(2025)

    Pith/arXiv arXiv 2025