Pith. sign in

REVIEW 3 major objections 4 minor 54 references

CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read CleANN claims graph-based vector search keeps static-build quality under inserts, deletes, and concurrent searches, with 7–1200x throughput gains over FreshVamana at equal recall.

desk verdict CleANN is a serious systems paper with real new mechanisms, but the paper's own data contradicts its strongest claim, and the main recall benchmark is partly in-sample. read the letter →

arxiv 2507.19802 v2 pith:VTB7U3YP submitted 2025-07-26 cs.DB cs.DCcs.DScs.IR

Ziyu Zhang , Yuanhao Wei , Joshua Engels , Julian Shun This is my paper · ORCID
classification cs.DBcs.DCcs.DScs.IR
keywords approximatenearestneighborsearchgraph-basedindexdynamicindexingconcurrentinsertsanddeletesslidingwindowvectordatabaserecallthroughput
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

The paper claims that a graph-based approximate nearest neighbor search index can be made fully dynamic—concurrent inserts, deletes, and searches—without the periodic global consolidation that previous dynamic indexes require. The proposed system, CleANN, is said to maintain query recall at least as good as an index rebuilt from scratch on the corresponding data, while achieving 7–1200x higher search throughput than FreshVamana at equal recall on million-scale datasets. Three mechanisms carry the argument: workload-aware bridge edges among nodes visited during search-tree exploration, on-the-fly consolidation around deleted nodes triggered by searches, and semi-lazy memory cleaning that recycles tombstones before all their incoming edges are fixed. If the claim holds, full dynamism stops being the weak point of graph-based ANNS and becomes a head-to-head contest with static rebuilds.

What carries the argument

The central object is the search tree T built during each GreedyBeamSearch traversal, together with the bridge-building step GuidedBridgeBuild that connects nodes at selected depths of T (typically Θ(log |D|) layers) subject to a heuristic predicate—in practice, endpoints at the same depth. These bridge edges restore the missing shortcuts that static builds obtain through global passes. For deletions, the key structure is the tombstone counter H(w), which counts how many times a deleted node has been consolidated by a live parent during a traversal; once H(w) exceeds an eagerness threshold C, the node becomes replaceable and can represent a new data point. Consolidation itself is the operation that copies a tombstone's out-neighborhood into the live parent's neighborhood (Algorithm 7). The entire CleANN system combines these on-the-fly repairs with the Vamana graph, using this machinery to avoid global consolidation entirely.

What would settle it

Run the sliding-window benchmark with training queries drawn from an earlier time window or from a separate held-out query set that is not derived from the test queries, and check whether CleANN still matches RebuildVamana recall on distribution-shift datasets such as RedCaps or MS-SpaceV; if the recall gap reappears, a significant part of the bridge-building advantage is an artifact of the training distribution.

Watch

Extended reading notes

Core claim

The central discovery is that the robustness problems of dynamic graph-based indexes can be solved locally and lazily rather than globally. During any beam search, the visited nodes form a search tree; adding a few edges between same-depth cousins in that tree—nodes that are nearby but lacked a short connection—dramatically improves navigability under adversarial insertion orderings. For deletions, the index does not need to connect every in-neighbor of a tombstone to every out-neighbor; instead, while traversing, a live node that encounters a tombstone absorbs the tombstone's out-neighborhood on the spot, and after a small number of such consolidations the tombstone is marked replaceable and reused for new data, even if some incoming edges still point at it. The paper argues that these random residual edges do little harm because beam search and pruning naturally ignore them. Together these mechanisms let CleANN match the recall of a freshly rebuilt index while avoiding the costly global scans that make prior dynamic indexes an order of magnitude slower.

Load-bearing premise

The measured recall parity assumes that the in-distribution training queries—generated by randomly sampling the actual test queries and perturbing them by a scale tied to the dataset's average nearest-neighbor distance—are a fair proxy for the query workload rather than a form of test-set adaptation.

Editorial extensions

If this is right

  • On sliding-window workloads, a graph-based index using CleANN's insertion and cleaning routines can match the recall of a freshly rebuilt static index without paying the rebuild cost.
  • Because cleaning is trigger-driven and local, searches and updates can run concurrently without a global scan, so throughput does not collapse while deletions are being processed.
  • The core techniques are portable: guided bridge building and on-the-fly consolidation apply to any graph-based ANNS index that uses beam search plus a pruning routine, not just Vamana.
  • On datasets with distribution shift or out-of-distribution queries, query-aware bridge building can push recall above a static rebuild on the same data.
  • At a fixed recall target, CleANN's throughput advantage over FreshVamana grows as the write share of the workload increases.

Reading between the lines

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

  • The reported recall parity on distribution-shift datasets depends on the training-query construction, which samples test queries and perturbs them; a cleaner evaluation would train on queries from an earlier time window and would reveal how much of the advantage is genuine adaptivity versus test-set adaptation.
  • The fact that a small training batch (2% of test queries) suffices suggests that only a few high-value edges carry most of the navigability; identifying which edges these are could let other indexes add bridges more cheaply.
  • The experiments are in-memory, so the benefits may not transfer to out-of-core settings where tombstones and random edges increase I/O; testing under a disk-based index or a memory cap would clarify the boundary of the claim.
  • If the bridge-building mechanism is as robust as claimed, it could also improve static index construction under non-uniform insertion orders, which would simplify build pipelines that currently require careful ordering or global passes.
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

3 major / 4 minor

Summary. The paper proposes CleANN, a concurrent dynamic graph-based approximate nearest neighbor search (ANNS) system built on Vamana/DiskANN. CleANN combines three techniques: guided bridge building, which adds edges between nodes at similar depths of the beam-search tree during inserts and training searches; on-the-fly neighborhood consolidation, which repairs the graph around tombstones when they are encountered during searches; and semi-lazy cleaning, which recycles tombstone nodes after a tunable number of consolidations without fully removing all dangling edges. The authors claim that CleANN achieves query quality at least as good as a static rebuild on fully dynamic sliding-window workloads, and that at the same recall level it achieves 7-1200x throughput improvements over FreshVamana on million-scale datasets. The evaluation covers 7 datasets, compares against RebuildVamana, FreshVamana, NaiveVamana, and DEG, and includes ablations, hyperparameter sensitivity, memory overhead, and scalability studies.

Significance. If the main claims hold, this would be a significant contribution: CleANN would be the first concurrent graph-based ANNS index that maintains static-build-quality recall under full dynamism without expensive global consolidation, while also supporting concurrent inserts, deletes, and searches. The paper is engineering-heavy but presents a coherent set of mechanisms with a publicly available implementation. Strengths include the breadth of datasets, the ablation studies (especially the no-training and memory-reuse experiments), the sensitivity analysis of the cleaning threshold C, and the direct comparison with the sequential DEG baseline. However, the headline quality and throughput claims are weakened by the evaluation design: training queries are derived from the test queries, and the throughput numbers are reported at approximately matched recall rather than exactly matched recall.

major comments (3)
  1. [Section 6.1, 'Sliding Window Batched Update'] The recall evidence for the central 'at least as good as static' claim is in-sample. The training queries used to activate GuidedBridgeBuild during searches are generated by 'randomly sampling from test queries and adding a perturbation parameterized by the average nearest neighbor distance'. Since GuidedBridgeBuild modifies the graph during training searches (Section 3.1.2, Algorithm 8, lines 29-30) and only the test queries are marked performance-sensitive, the index is explicitly adapted to a distribution that is deliberately close to the test distribution before recall is measured. On datasets with distribution shift or out-of-distribution queries (RedCaps, Yandex-tti, Adversarial, MS-SpaceV), the reported recall advantage may therefore reflect test-set adaptation rather than robust dynamic maintenance. The no-training variant in Figure 37 provides partial independent evidence, and the ablation in Figure 36 does not use the training phase, but the main benchmark numbers in Table 3 and Figures 6-12 all use this in-sample training regime. Please report the main recall comparisons for a no-training configuration, or with held-out queries that are disjoint from the training queries, and state clearly whether the quality claim applies to the query-adapted setting only.
  2. [Table 3, rows Sift and MS-SpaceV] The unqualified abstract claim that 'CleANN has query quality at least as good as if the index had been built statically' is contradicted by the paper's own Table 3: CleANN's recall is below RebuildVamana on Sift (98.81% vs. 98.98%) and on MS-SpaceV (89.54% vs. 89.72%), and below FreshVamana on four of the seven datasets (Sift, MS-SpaceV, RedCaps, HuffPost). The gaps are small, but the claim as stated is not supported. Either qualify the claim (e.g., 'competitive with' or 'within measurement noise of') or provide statistical significance or repeated-run variability to justify the 'at least as good' phrasing.
  3. [Section 6.2 and Table 3, throughput comparison] The throughput claims are reported at 'approximately matched' recall, not at exactly the same recall level. Table 3 states that 'Other parameters are varied to approximately match the recalls of different approaches.' Since the abstract claims 'at the same recall level', the 7-1200x speedup numbers could change if recalls were exactly matched, especially on datasets where CleANN's recall is slightly lower. Please present throughput at several matched recall levels (e.g., by interpolating the recall-throughput tradeoff curves in Figures 22-33) or report the recall values used for each throughput number so the reader can judge the size of the recall gaps.
minor comments (4)
  1. [Section 6.3.1, Figures 22-33] Several figure captions appear to be duplicated or mismatched with the surrounding text: for example, Figure 23 is captioned 'on RedCaps' while the text refers to GloVe, and Figure 25 says 'RedCaps' in the caption but the text references GloVe. Please re-check the correspondence between figures and captions.
  2. [Table 3 and Figures 6-19] The index sizes used in the main benchmark are inconsistent between Table 3 and the figure captions: for instance, Table 3 lists Sift at 150k and RedCaps at 1.5M used, while Figures 6 and 9 captions state index sizes of 50k and 500k respectively. Please clarify which index sizes correspond to which experimental round and how the 'Size Used' column relates to the sliding-window initial size.
  3. [Section 6.2.2] The phrase 'maintains a similar recall as CleANN' for FreshVamana is imprecise; the recall differences in Figures 6-12 are up to several percentage points. Please state numeric recall ranges or use a consistent 'matched recall' protocol for the throughput comparison.
  4. [Section 6.1] When search throughput is reported for the Sliding Window Mixed Update setting, the text says the weighted average across training and test queries is used. Please state explicitly what fraction of the reported throughput corresponds to training queries and how much the GuidedBridgeBuild overhead in those queries contributes to the reported numbers.

Circularity Check

1 steps flagged · score 6.0 of 10

The headline recall claim is in-sample: training queries are generated by perturbing the test queries, so the 'at least as good as static' comparison is partly self-referential.

  1. fitted input called prediction [Section 6.1 'Sliding Window Batched Update' and Section 6.2.1 (Table 3, Figures 6-12)]
    "Since GuidedBridgeBuild learns from queries, to avoid training and testing on the same queries, we issue a separate batch of in-distribution training queries generated by randomly sampling from test queries and adding a perturbation parameterized by the average nearest neighbor distance in the dataset before we issue the test queries. The size of the training query set is 2% of the test set (except for RedCaps, which uses 80 training queries). We designate only test queries as performance sensitive in Algorithm 8."

    The paper's central quality claim, that CleANN 'has query quality at least as good as if the index had been built statically,' is established by computing recall on the test queries after GuidedBridgeBuild has already adapted the graph during search queries that are random perturbations of those same test queries. The perturbation is tied to the dataset's average nearest-neighbor distance, so the training distribution is deliberately adjacent to the test distribution. Figure 37 confirms the effect is substantial: in-distribution training gives up to 18% higher recall than no training. Thus the reported recall advantage on distribution-shift and OOD datasets reflects in-sample adaptation to the test distribution rather than an out-of-sample property of the dynamic maintenance scheme.

full rationale

CleANN's algorithmic components are not circular by construction: GuidedBridgeBuild, on-the-fly neighborhood consolidation, and semi-lazy cleaning are defined in terms of search-tree structure, tombstone counts, and consolidation thresholds, not in terms of the target recall values, and the ablations in Figures 35-40 provide some independent evidence for each mechanism. The main circularity concern is experimental. Section 6.1 generates 'in-distribution training queries' by randomly sampling the test queries and adding a perturbation scaled by the average nearest-neighbor distance. Because GuidedBridgeBuild is executed during these training searches (Algorithm 8, lines 29-30) and only test queries are marked performance-sensitive, the graph is adapted to a distribution artificially close to the test queries before the same test queries are scored. The headline claim of static-quality matching is therefore evaluated in-sample for datasets with distribution shift and out-of-distribution queries. Figure 37 quantifies that in-distribution training raises recall by up to 18% over no training, so a large part of the reported advantage is test-set adaptation. The no-training ablation gives partial support for the core mechanism, and the throughput results are less affected because they are measured in the mixed-update setting where recall is not directly measured. Separately, Table 3 shows CleANN recall below RebuildVamana on Sift (98.81% vs 98.98%) and MS-SpaceV (89.54% vs 89.72%), which contradicts the unqualified abstract phrasing but is a correctness issue rather than circularity. Overall, no derivation step reduces to its own inputs by equation; the evaluation of the central quality claim is partially self-referential.

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

The central claims rest on several empirical assumptions that are tested on the paper's chosen datasets but not proven. The most consequential is the use of test-derived training queries, which makes the headline recall comparisons partially self-referential. The remaining assumptions (per-tombstone consolidation threshold, random-edge safety) are engineering heuristics backed by ablation studies rather than proofs.

free parameters (4)
  • Cleaning eagerness threshold C = 7
    Number of consolidations before a tombstone becomes replaceable; sensitivity studied in Section 6.3.5.
  • Bridge layer set S = {log2|D|+2, log2|D|+3, log2|D|+4}
    Search-tree depths at which bridge edges are added; chosen experimentally in Section 3.1.3.
  • Perturbation scale for training queries = average nearest neighbor distance of the dataset
    Used in Section 6.1 to generate in-distribution training queries from test queries; this couples the training distribution to the test set.
  • Vamana hyperparameters L, L_I, R, alpha = L=75, L_I=64, R=64, alpha=1.2 by default; varied to match recall in Table 3
    Inherited from Vamana, but varied in the comparisons that support the 'at the same recall level' throughput claim.
assumptions (4)
  • domain assumption Graph-based ANNS with greedy beam search and alpha-RNG pruning behaves as in prior work (Vamana, DiskANN).
    The paper builds on DiskANN's Vamana index and assumes its construction and search algorithms are correct and effective.
  • domain assumption A constant number (C=7) of on-the-fly consolidations per tombstone preserves graph navigability as well as global consolidation.
    Section 4.1 introduces early stopping; sensitivity analysis in Section 6.3.5 is empirical only, no bound or proof is given.
  • domain assumption Leftover random edges from reused graph nodes do not materially degrade query quality.
    Semi-lazy cleaning relies on this; validated only empirically in Section 6.3.6.
  • ad hoc to paper Training queries perturbed from the test set are representative of the test workload.
    Section 6.1 generates training queries from the same test queries, which makes the main recall numbers partially in-sample.

how reviews work

0 comments
Cite this review

Pith. "Pith review of CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/VTB7U3YP

@misc{pith2026250719802,
  author       = {Pith},
  title        = {Pith review of: CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VTB7U3YP}},
  note         = {Machine review of arXiv:2507.19802}
}
read the original abstract

Approximate nearest neighbor search (ANNS) has become a quintessential algorithmic problem for various other foundational data tasks for AI workloads. Graph-based ANNS indexes have superb empirical trade-offs in indexing cost, query efficiency, and query approximation quality. Most existing graph-based indexes are designed for the static scenario, where there are no updates to the data after the index is constructed. However, full dynamism (insertions, deletions, and searches) is crucial to providing up-to-date responses in applications using vector databases. It is desirable that the index efficiently supports updates and search queries concurrently. Existing dynamic graph-based indexes suffer from at least one of the following problems: (1) the query quality degrades as updates happen; and (2) the graph structure updates used to maintain the index quality upon updates are global and thus expensive. To solve these problems, we propose the CleANN system which consists of three main components: (1) workload-aware linking of diverse search tree descendants to combat distribution shift; (2)query-adaptive on-the-fly neighborhood consolidation to efficiently handle deleted nodes; and (3) semi-lazy memory cleaning to clean up stale information in the data structure and reduce the work spent by the first two components. We evaluate CleANN on 7 diverse datasets on fully dynamic workloads and find that CleANN has query quality at least as good as if the index had been built statically using the corresponding data. In the in-memory setting using 56 hyper-threads, with all types of queries running concurrently, at the same recall level, CleANN achieves 7-1200x throughput improvement on million-scale real-world datasets. To the best of our knowledge, CleANN is the first concurrent ANNS index to achieve such efficiency while maintaining quality under full dynamism.

Figures

Figures reproduced from arXiv: 2507.19802 by the authors.

Figure 1
Figure 1. Search throughput and av￾erage recall with (FreshVamana) or without (NaiveVamana) concurrent global consolidation. The datasets are described in section 6. 0 20 40 60 80 100 Batch 0.1 0.2 0.3 0.4 0.5 Recall 10@10 FreshVamana (bad ordering) RebuildVamana (bad ordering) FreshVamana (good ordering) CleANN (bad ordering) RebuildVamana (good ordering) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Step-by-step illustration of RobustInsert (Algorithm 6). Algorithm 7 Consolidation (Subroutine of Algorithm 2 in [45]) 1: 𝑅 : Global out-degree bound 2: procedure Consolidate(𝑣) 3: C = ∅ // Neighbor Candidates 4: for 𝑤 ∈ 𝑁 (𝑣) do 5: if IsLive(𝑤) then 6: C = C ∪ {𝑤} 7: else C = C ∪ {𝑢 ≠ 𝑣 ∧ IsLive(𝑢) | 𝑢 ∈ 𝑁 (𝑤) } 8: if | C | < R then 𝑁 (𝑣) = C 9: else 𝑁 (𝑣) = RobustPrune(𝑣, C ) data structure and concurrent operatio… view at source ↗
Figure 4
Figure 4. 𝑥 is the data point be￾ing deleted (𝑤𝑥 is the correspond￾ing node). Blue edges existed prior to the deletion. Red edges are added during CleanConsolidation. Solid edges exist after the consolidation fin￾ishes and 𝑤𝑥 is marked as replaceable. Dashed edges are deleted. wx v2 o2 o1 o3 v1 v3 wy u1 u2 p1 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figures from the paper (15 more)
Figure 6
Figure 6. Figure 6: Recall over updates for Sift with index size 50k. 0 50 100 150 200 Round 0.5 0.6 0.7 0.8 0.9 Recall 50@50 RebuildVamana FreshVamana CleANN NaiveVamana [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 8
Figure 8. Figure 8: Recall over updates for Huff￾Post with index size 50k. 0 50 100 150 200 Round 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Recall 50@50 RebuildVamana FreshVamana CleANN NaiveVamana [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 10
Figure 10. Figure 10: Recall over updates for SpaceV with index size 500k. 0 50 100 150 200 Round 0.5 0.6 0.7 0.8 0.9 Recall 50@50 RebuildVamana FreshVamana CleANN NaiveVamana [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]
Figure 12
Figure 12. Figure 12: Recall over updates for Ad￾versarial with index size 50k. hyper-threads. These results are shown in [PITH_FULL_IMAGE:figures/full_fig_p011_12.png]
Figure 20
Figure 20. Figure 20: Recall on RedCaps with an index of size 500,000 of CleANN, FreshVamana, and DEG with 𝜀 = 0.03. CleANN L64 DEG ε 0.03 Algorithm 0.00 0.05 0.10 0.15 0.20 0.25 Throughput (updates / ms) Search Update [PITH_FULL_IMAGE:figures/full_fig_p011_20.png]
Figure 22
Figure 22. Figure 22: Tradeoff between average search throughput and recall at round 100 on Sift with index size 50k. (Higher and to the right is better.) 0.7 0.8 0.9 Recall 0 10 20 30 40 50 Update Throughput (operations / ms) Recall vs Update Throughput Tradeoff CleANN NaiveVamana FreshVa…
Figure 24
Figure 24. Figure 24: Tradeoff between average search throughput and recall at round 100 on RedCaps with index size 500k. (Higher and to the right is better.) 0.60 0.65 0.70 0.75 0.80 Recall 0 10 20 30 40 50 Update Throughput (operations / ms) Recall vs Update Throughput Tradeoff CleANN Na…
Figure 26
Figure 26. Figure 26: Tradeoff between average search throughput and recall at round 100 on HuffPost with index size 50k. (Higher and to the right is better.) 0.7 0.8 0.9 Recall 0 2 4 6 8 10 Update Throughput (operations / ms) Recall vs Update Throughput Tradeoff CleANN NaiveVamana FreshVa…
Figure 34
Figure 34. Figure 34: Update and Search throughput of MS-SpaceV under Sliding Window [PITH_FULL_IMAGE:figures/full_fig_p012_34.png]
Figure 40
Figure 40. Figure 40: Overall throughput in Slid￾ing Window Mixed Update over a sliding window of 500,000 MS-SpaceV points. The lines for RebuildVamana and FreshVamana are overlapping. 600,000 vectors, so that new data points cannot avoid reusing mem￾ory from semi-lazy memory cleaning. The…
Figure 37
Figure 37. Figure 37: Recall 10@10 on RedCaps for different variations of using train￾ing queries. 10 30 50 70 90 Percentage of Queries used for Training 80 82 84 86 88 90 92 Average recall 10@10 RedCaps MS-SpaceV [PITH_FULL_IMAGE:figures/full_fig_p013_37.png]
Figure 41
Figure 41. Figure 41: Average throughput and re￾call for Adversarial with index size 500k for different values of 𝐶. 0 20 40 60 C 0.770 0.775 0.780 0.785 0.790 Recall 50@50 Recall 10 11 12 13 14 Search Throughput (operations / ms) Search Throughput [PITH_FULL_IMAGE:figures/full_fig_p014_41.png]
Figure 43
Figure 43. Figure 43: Average throughput and re￾call for HuffPost with index size 50k for different values of 𝐶. 0 20 40 60 C 0.56 0.58 0.60 0.62 Recall 50@50 Recall 12 14 16 18 Mixed Throughput (operations / ms) Throughput [PITH_FULL_IMAGE:figures/full_fig_p014_43.png]
Figure 45
Figure 45. Figure 45: Average throughput and re￾call for Sift with index size 500k for different values of 𝐶. 0 20 40 60 C 0.88 0.89 0.90 Recall 50@50 Recall 6.0 6.5 7.0 7.5 Mixed Throughput (operations / ms) Throughput [PITH_FULL_IMAGE:figures/full_fig_p014_45.png]
Figure 47
Figure 47. Figure 47: Average throughput and re￾call for Yandex-tti with index size 500k for different values of 𝐶. recall controlling the Search and graph construction parameters (𝐿, 𝐿𝐼 , 𝑅). Figures 48 and 49 present the results. In the "Memory not Reused" setting, we provision enough gr…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 26 canonical work pages

  1. [1]

    [n. d.]. big-ann-benchmarks/neurips23/streaming at main · harsha-simhadri/big- ann-benchmarks — github.com. https://github.com/harsha-simhadri/big-ann- benchmarks/tree/main/neurips23/streaming. [Accessed 01-10-2024]

    work page 2024

  2. [2]

    [n. d.]. YouTube for Press. https://blog.youtube/press/ Accessed on September 24, 2024

    work page 2024

  3. [3]

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2018. ANN- Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algo- rithms. arXiv:1807.05614 [cs.IR] https://arxiv.org/abs/1807.05614

    arXiv 2018

  4. [4]

    Dimitry Baranchuk and Artem Babenko. [n. d.]. Yandex — research.yandex.com. https://research.yandex.com/datasets/text-to-image-dataset-for-billion-scale- similarity-search. [Accessed 30-07-2024]

    work page 2024

  5. [5]

    Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion- scale Approximate Nearest Neighbor Search. CoRR abs/2111.08566 (2021). arXiv:2111.08566 https://arxiv.org/abs/2111.08566

    arXiv 2021

  6. [6]

    Yewang Chen, Shengyu Tang, Nizar Bouguila, Cheng Wang, Jixiang Du, and HaiLin Li. 2018. A fast clustering algorithm based on pruning unnecessary dis- tance computations in DBSCAN for high-dimensional data. Pattern Recognition 83 (2018), 375–387

    work page 2018

  7. [7]

    SpaceV Contributors. 2023. SPTAG/datasets/SPACEV1B at main · mi- crosoft/SPTAG — github.com. https://github.com/microsoft/SPTAG/tree/main/ datasets/SPACEV1B. [Accessed 30-07-2024]

    work page 2023

  8. [8]

    Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. 2011. Fast locality-sensitive hashing. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (San Diego, California, USA) (KDD ’11). Association for Computing Machinery, New York, NY, USA, 1073–1081. https: //doi.org/10.1145/2020408.2020578

    arXiv 2011

Show all 54 references
  1. [9]

    Sanjoy Dasgupta and Kaushik Sinha. 2015. Randomized Partition Trees for Nearest Neighbor Search. Algorithmica 72, 1 (01 May 2015), 237–263. https: //doi.org/10.1007/s00453-014-9885-5

    2015 doi

  2. [10]

    Mirrokni

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry (Brooklyn, New York, USA) (SCG ’04). Association for Computing...

    2004

  3. [11]

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

    2019

  4. [12]

    Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB ’99) . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 518–529

    1999

  5. [13]

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In International Conference on Machine Learning . https: //arxiv.org/abs/1908.10396

    2020 arXiv

  6. [14]

    Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 5713–5722. https://doi.org/10.1109/CVPR.2016.616

    2016 doi

  7. [15]

    Nico Hezel, Uwe Kai Barthel, Konstantin Schall, and Klaus Jung. 2023. Fast Approximate nearest neighbor search with the Dynamic Exploration Graph using continuous refinement. CoRR abs/2307.10479 (2023)

    2023 arXiv

  8. [16]

    Linjia Hu, Saeid Nooshabadi, and Majid Ahmadi. 2015. Massively parallel KD-tree construction and nearest neighbor search algorithms. In 2015 IEEE International Symposium on Circuits and Systems (ISCAS) . 2752–2755. https://doi.org/10.1109/ ISCAS.2015.7169256

    2015

  9. [17]

    HuffPost, Rishabh Misra, and Ziyu Zhang. 2024. Embedded HuffPost New Category Dataset

    2024

  10. [18]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (Dallas, Texas, USA) (STOC ’98). Association for Computing Machinery, New York, NY, USA...

    1998

  11. [19]

    Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data. arXiv:1810.07355 [cs.DB] https://arxiv.org/abs/1810.07355

    2018 arXiv

  12. [20]

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Zhang et al. Nearest Neighbor Search on a Single Node. InAdvances in Neural Information Pro- cessing Systems, H. Wallach, H. ...

    2019

  13. [22]

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

    2025 doi

  14. [23]

    Jaemin Jo, Jinwook Seo, and Jean-Daniel Fekete. 2017. A progressive k-d tree for approximate k-nearest neighbors. In 2017 IEEE Workshop on Data Systems for Interactive Analysis (DSIA). 1–5. https://doi.org/10.1109/DSIA.2017.8339084

    2017

  15. [24]

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

    2011 doi

  16. [25]

    Mohammad Kolahdouzan and Cyrus Shahabi. 2004. Voronoi-based K nearest neighbor search for spatial network databases. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB ’04). VLDB Endowment, 840–851

    2004

  17. [26]

    Kuan and P

    J. Kuan and P. Lewis. 1997. Fast k nearest neighbour search for R-tree fam- ily. In Proceedings of ICICS, 1997 International Conference on Information, Com- munications and Signal Processing. Theme: Trends in Information Systems Engi- neering and Wireless Multimedia Communicat...

    1997

  18. [27]

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2021. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. arXiv:2005.1140...

    2021 arXiv

  19. [28]

    Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The design and implementation of a real time visual search system on JD E-commerce platform. In Proceedings of the 19th International Middleware Conference Industry. 9–16

    2018

  20. [29]

    Sen Li, Fuyu Lv, Taiwei Jin, Guli Lin, Keping Yang, Xiaoyi Zeng, Xiao-Ming Wu, and Qianli Ma. 2021. Embedding-based product retrieval in taobao search. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 3181–3189

    2021

  21. [30]

    Ting Liu, Andrew Moore, Ke Yang, and Alexander Gray. 2004. An Investiga- tion of Practical Approximate Nearest Neighbor Algorithms. In Advances in Neural Information Processing Systems , L. Saul, Y. Weiss, and L. Bottou (Eds.), Vol. 17. MIT Press. https://proceedings.neurips.c...

    2004

  22. [31]

    Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. Proc. VLDB Endow. 15, 2 (oct 2021), 246–258. https: //doi.org/10.14778/3489496.3489506

    2021

  23. [32]

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

  24. [33]

    Malkov and D

    Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824–

    2020

  25. [34]

    Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms. In Proceedings of the 29th ACM SIGPLAN Annual S...

    2024

  26. [35]

    Rajeev Motwani, Assaf Naor, and Rina Panigrahi. 2006. Lower bounds on locality sensitive hashing. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (Sedona, Arizona, USA) (SCG ’06) . Association for Computing Machinery, New York, NY, USA, 154–157. ...

    2006

  27. [36]

    Felix Ocker, Daniel Tanneberg, Julian Eggert, and Michael Gienger. 2024. Tulip Agent–Enabling LLM-Based Agents to Solve Tasks Using Large Tool Libraries. arXiv preprint arXiv:2407.21778 (2024)

    2024 arXiv

  28. [37]

    Apostolos Papadopoulos and Yannis Manolopoulos. 1997. Performance of nearest neighbor queries in R-trees. In Database Theory — ICDT ’97 , Foto Afrati and Phokion Kolaitis (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 394–408

    1997

  29. [38]

    Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. GloVe: Global Vectors for Word Representation. InProceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) , Alessandro Mos- chitti, Bo Pang, and Walter Daelemans (Eds.). As...

    2014 doi

  30. [39]

    Erion Plaku and Lydia E Kavraki. 2008. Quantitative analysis of nearest-neighbors search in high-dimensional sampling-based motion planning. In Algorithmic Foundation of Robotics VII: Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations o...

    2008

  31. [40]

    Parikshit Ram and Kaushik Sinha. 2019. Revisiting kd-tree for Nearest Neigh- bor Search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (Anchorage, AK, USA) (KDD ’19). As- sociation for Computing Machinery, New York, NY, USA...

    2019

  32. [41]

    Reddit, Karan Desai, Gaurav Kaul, Zubin Aysola, Justin Johnson, Joshua Engels, Ziyu Zhang, and OpenAI (United States). 2024. CLIP-Embedded RedCaps Text- Image Dataset

    2024

  33. [42]

    Aviad Rubinstein. 2018. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles, CA, USA) (STOC 2018). Association for Computing Machinery, New York, NY, USA, 1260–1268. https://doi.org/10.1145...

    2018

  34. [43]

    Maying Shen, Xinghao Jiang, and Tanfeng Sun. 2018. Anomaly detection based on nearest neighbor search with locality-sensitive B-tree. Neurocomputing 289 (2018), 55–67

    2018

  35. [44]

    Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, Andrija Antonijevic, Dax Pryce, David Kaczynski, Shane Williams, Siddarth Gollapudi, Varun Sivashankar, Neel Karia, Aditi Singh, Shikhar Jaiswal, Neelam Mahapatro, Philip Adams, Bryan...

  36. [45]

    Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Har- sha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph- Based ANN Index for Streaming Similarity Search. arXiv:2105.09613 [cs.IR] https://arxiv.org/abs/2105.09613

    2021 arXiv

  37. [46]

    Ján Suchal and Pavol Návrat. 2010. Full text search engine as scalable k-nearest neighbor recommendation system. In Artificial Intelligence in Theory and Practice III: Third IFIP TC 12 International Conference on Artificial Intelligence, IFIP AI 2010, Held as Part of WCC 2010,...

    2010

  38. [47]

    Philip Sun, David Simcha, Dave Dopson, Ruiqi Guo, and Sanjiv Kumar. 2023. SOAR: Improved Indexing for Approximate Nearest Neighbor Search. In Neural Information Processing Systems. https://arxiv.org/abs/2404.00774

    2023 arXiv

  39. [48]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A com- prehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow. 14, 11 (jul 2021), 1964–1978. https://doi.org/10.14778/3476249.3476255

    2021

  40. [49]

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

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

    2025 arXiv

  41. [50]

    Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In Proceedings of the 29th Symposium on Operating Systems Prin...

    2023

  42. [51]

    Fangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi, Hua Fan, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 3, Article 152 (June 2025), 26 pages. https://doi.org/10.1...

    2025 doi

  43. [52]

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

    2023

  44. [836]

    https://doi.org/10.1109/TPAMI.2018.2889473

    2018

  45. [2014]

    Information Systems 45 (2014), 61–68

    Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68. https://doi.org/10.1016/j.is.2013. 10.006

    2014 doi

  46. [2023]

    https://github.com/Microsoft/DiskANN

    DiskANN: Graph-structured Indices for Scalable, Fast, Fresh and Filtered Approximate Nearest Neighbor Search. https://github.com/Microsoft/DiskANN

Pith tools

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