EnhanceGraph: A Continuously Enhanced Graph-based Index for High-dimensional Approximate Nearest Neighbor Search

Haoyang Li; Heng Tao Shen; Jiabao Jin; Jingkuan Song; Mingyu Yang; Peng Cheng; Xiaoyao Zhong; Zhitao Shen

REVIEW 4 major objections 5 minor 50 references

EnhanceGraph: A Continuously Enhanced Graph-based Index for High-dimensional Approximate Nearest Neighbor Search

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

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

Pith's one-line read Replaying failed searches lifts ANN recall from 42% to 93%

desk verdict Genuinely novel log-driven graph enhancement with solid empirical gains; the missing theorem and same-distribution test queries are the main soft spots. read the letter →

arxiv 2506.13144 v2 pith:PAPUXCE2 submitted 2025-06-16 cs.DB

Xiaoyao Zhong , Jiabao Jin , Peng Cheng , Mingyu Yang , Haoyang Li , Zhitao Shen , Heng Tao Shen , Jingkuan Song This is my paper · ORCID

classification cs.DB

keywords approximatenearestneighborsearchgraph-basedindexconjugategraphlogconstructionrecallimprovementVoronoicellhigh-dimensionalindexing

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

EnhanceGraph argues that graph-based approximate nearest neighbor indexes need not stay static after construction: the failures and near-misses recorded while serving queries, plus the edges discarded during construction, contain exactly the information needed to fix the index. The paper proposes a conjugate graph attached to any proximity graph, storing routing edges from local optima to global optima (from search logs) and pruned k-NN edges (from construction logs). At query time, after the ordinary greedy search stalls at a local optimum, the conjugate graph redirects the search to the true nearest neighbor and supplies the missing k nearest neighbors. The claimed payoff is a large recall gain at essentially unchanged query throughput, with the largest reported improvement from 41.74% to 93.42% Recall@1 on GIST1M.

What carries the argument

The load-bearing object is the conjugate graph $G'$, a directed companion to the proximity graph $G$ that is not used for routing during the main search. It stores two kinds of edges: routing edges $(x_l, x_g)$ from a local optimum to the global optimum found in the search log, and non-routing edges that were pruned during construction, so that $G'[x_b]$ holds the discarded candidates from the construction log. Update (Algorithm 3) generates error-prone query points $x_e = \omega x_b + (1-\omega)x_k$ near the boundary of the base point's Voronoi cell, greedily searches them, and records $(x_l, x_g)$ whenever the local optimum misses the base point. At query time, Algorithm 2 first runs the ordinary greedy search, then takes the neighbors of the local optimum and of the recovered global optimum in $G'$ and merges them into the candidate set, which is equivalent to raising the search list size by about two.

What would settle it

Take a high-dimensional dataset (or a synthetic one with engineered nearest-neighbor layouts), generate queries $x_e = \omega x_b + (1-\omega)x_k$ for $\omega>0.5$, and test whether $x_b$ is the exact nearest neighbor of $x_e$. If a large fraction of generated queries fail that test, Algorithm 3 writes conjugate edges to a point that is not the global optimum, and the reported Recall@1 gains should shrink or reverse on those queries.

Watch

Extended reading notes

Core claim

The paper's central claim is that a static proximity graph's two recurring failure modes can be diagnosed and repaired from data the index itself generates. When a greedy search stops at a local optimum $x_l$ instead of the true nearest neighbor $x_g$, many similar queries converge to that same $x_l$; recording the missing edge $(x_l, x_g)$ in a conjugate graph lets every later query that reaches $x_l$ step directly to $x_g$. Similarly, when construction prunes legitimate k-NN edges, storing those pruned edges in the same conjugate graph and reading them after the global optimum is found lifts Recall@k. The paper backs this with a theorem (with positive recall, the local optimum lies in the true k-NN set), with observations that local optima are usually close neighbors of the global optimum and that similar queries share local optima, and with a query-generation scheme placing synthetic queries near Voronoi cell boundaries to expose flaws. On top of existing graph indexes such as HNSW, NSG, Vamana, and tau-MNG, the framework reports consistent recall improvements at comparable query-per-second rates.

Load-bearing premise

The framework depends on the claim that a query produced along the segment between a base point and one of its nearest neighbors actually falls inside the base point's Voronoi cell, so the base point is that query's true nearest neighbor; the paper notes this is only guaranteed in most cases, when the two cells are adjacent.

Editorial extensions

If this is right

Applying EnhanceGraph to a graph index raises Recall@1 substantially where the baseline is weak; the paper reports the largest jump from 41.74% to 93.42% on GIST1M.
The same conjugate graph lifts Recall@10 because the stored construction-log edges restore pruned k-NN connections once the global optimum is reached.
Because the conjugate graph is consulted only after the proximity-graph search ends, the throughput cost is roughly that of increasing the search parameter L by 2, not a full re-run.
The framework is index-agnostic: it works by wrapping an existing graph index rather than building a new proximity graph from scratch, and it is demonstrated on four established graph indexes.
The benefit is tied to the search parameter used when collecting logs: at query time, using a list size L larger than the logged L2 can overshoot the logged local optimum and miss the conjugate edge, so the method is most effective near the logged operating point.

Reading between the lines

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

If the effect holds in production, a deployment could close the loop: every failed query logged during serving becomes a training edge, so the index improves with age rather than staying fixed at a known-bad state.
The same two-phase idea could be transplanted to partition-based and compressed indexes, where the 'local optimum' would be the best cell or bucket reached and the conjugate step would cross to better cells using logged failures.
The Voronoi-boundary query generator suggests a testable diagnostic for index health: the distribution of distances from generated points to their labelled global optimum measures how often the weakest assumption actually breaks in high dimensions.
A natural stress test is distribution shift: if new queries no longer resemble the logged ones, the conjugate edges become stale, and an adaptive version should retrain the conjugate graph from recent logs.

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.

Desk Editor's Note

read the letter

Colleague,

The short version: this paper has a genuinely useful idea and a hole in its theory. The conjugate graph—a side structure that stores pruned construction edges and search-log shortcuts from local optima to global optima—is new as far as the cited literature goes, and it works in the reported experiments. Four base indexes, eight datasets, consistent Recall@1 and Recall@10 gains at roughly unchanged QPS, modest memory overhead, and an industrial integration. The cost argument is sound: at most two extra nodes' neighbors are examined per query.

What is actually new is the combination of the two logs. Construction logs are usually discarded after pruning; search logs are usually ignored entirely. Using them together as a small second graph is simple and effective. The paper also deserves credit for the L2 dependence analysis—it clearly shows the conjugate graph only pays off when the search converges to the same local optimum as during log collection.

The soft spots are real but proportionate. The self-generated query heuristic (x_e = ω x_b + (1−ω) x_k) only guarantees x_e is closer to x_b than to x_k, not that x_e lies in x_b's Voronoi cell. The paper admits this—'in most cases'—and then promises a theorem that never appears. The text says 'we have the following theorem' and then moves on. That is a missing formal piece, not a fatal flaw, because Figure 11 empirically shows the local optima are usually the base point or its nearest neighbor; but the guarantee is absent and the mislabeling rate on high-dimensional data is unmeasured.

The more serious evaluation issue: the public-benchmark test queries are synthetic, generated from the same distribution as the historical search log used to build the conjugate graph. That is the right setup for an industrial system where the log matches the future workload, but it makes the headline numbers (41.74% to 93.42% on GIST1M) not directly comparable to standard ANN bench results. The authors should report on the original query sets, or at least present both.

No code or commit hash is provided, so the claims are not independently reproducible from the paper alone.

Bottom line: the core idea is sound and the experiments are extensive, but the missing theorem and the distributional overlap need to be addressed. This deserves a serious referee, with major revision. I'd bring it to reading group and I'd cite it if I worked in this area.

Referee Report

4 major / 5 minor

Summary. The paper proposes EnhanceGraph, a framework that augments a static graph-based ANNS index with a secondary ``conjugate graph.'' The conjugate graph stores two kinds of logged information: pruned edges from the construction process, and routing edges from search-log local optima to their presumed global optima. At query time, a standard greedy search runs on the proximity graph, and then the conjugate graph is used to hop from the local optimum to the global optimum and to supplement the k-NN result. The authors instantiate the framework on NSG, VAMANA, τ-MNG, and HNSW and report consistent Recall@1 and Recall@10 improvements across eight datasets, with the headline GIST1M Recall@1 gain from 41.74% to 93.42% at essentially unchanged QPS. The framework has been integrated into Ant Group's VSAG library.

Significance. If the claimed effect is real, EnhanceGraph is a practically valuable and general contribution: it turns byproduct logs into a cheap, index-agnostic accuracy booster, and the reported gains are consistent across multiple base indexes and datasets. The paper also ships a concrete implementation path (VSAG) and a simple, sound cost observation for Algorithm 2: only the neighbor lists of the local optimum and the global optimum are touched in the conjugate-graph stage. However, the central mechanism for self-generated search logs depends on an unproven Voronoi-adjacency assumption, and the promised correctness theorem is absent from the text. These issues bear directly on whether the reported recall gains can be attributed to correctly labeled routing edges or to a distributional artifact of the experimental setup.

major comments (4)

[Section IV-B and Algorithm 3 (lines 6-10)] The correctness of the self-generated labels rests on the claim that x_e = ω·x_b + (1−ω)·x_k lies in the Voronoi cell of x_b. Equation (1) only guarantees that x_e is closer to x_b than to x_k; it does not rule out a third base point x_t with dis(x_t, x_e) < dis(x_b, x_e). The paper itself concedes this holds only ``in most cases (i.e., when the two cells are adjacent),'' and no empirical evidence on the eight datasets is provided for cell adjacency or for the fraction of generated x_e whose exact nearest neighbor is x_b. When x_e falls outside VD(x_b), Algorithm 3 line 8 labels as ``global optimum'' the point argmin over ANN_{k_g}(x_b)∪{x_b}, which is not the true nearest neighbor, and the inserted edge (x_l, x_g) routes future queries to a wrong target. Because the large GIST1M gains depend on these edges, this is a load-bearing assumption. I ask the authors to either supply a proof under explicitly stated conditions or, more feasibly, measure empirically the fraction of generated queries whose exact NN is x_b on each dataset and show that mislabeled edges do not degrade recall.
[Section V-A, after Algorithm 3] The text states, ``We have the following theorem to guarantee the accuracy of the nearest neighbor search with our EnhanceGraph framework,'' but the theorem statement and proof are missing; the paragraph immediately moves to an approximation caveat. This is not a stylistic gap: it is the only place where the paper promises a formal justification for why self-generated routing edges cannot mislead the second-stage search. Please either state and prove the theorem, or explicitly replace the promise with a statement that Algorithm 3 is a heuristic whose validity is empirical.
[Section VI-A, Implementation, and Table III] For the public datasets, the synthetic historical search log and the test queries are generated from the same distribution: both add noise sampled from U(−0.5η, 0.5η) to base vectors, with only the requirement that test queries do not coincide with historical ones. This distributional alignment means the reported gains, including GIST1M 41.74%→93.42%, may substantially overstate performance on ad-hoc or out-of-distribution queries. The FACE experiment, which uses real historical queries, shows a much smaller gain (99.8%→99.9%). Please evaluate with standard benchmark query sets or another held-out distribution, and clarify how the global-optimum labels for the synthetic logs were obtained (exact ground truth vs. approximate search).
[Section IV-B and Table I] The Voronoi argument in Section IV-B is formulated in Euclidean space, but FACE and GloVe datasets use Inner Product and Angular distances. For these metrics the ``Voronoi cell'' of a point is not the Euclidean cell used in the derivation, and the interpolation x_e = ω·x_b + (1−ω)·x_k has no clear geometric interpretation under the actual distance. The paper should either extend the argument to the relevant distance functions or restrict the self-generated-query claim to Euclidean datasets and justify the experimental transfer separately.

minor comments (5)

[Algorithm 3, line 4] The approximate k_g-NN set ANN_{k_g}(x_b) is used as a substitute for exact k-NNs when generating queries. Please state which construction-log search parameters produce this set and whether any filtering is applied to remove points that are not true k-NNs.
[Section V-A, Discussion] The sentence ``The resulting QPS reduction is equivalent to increasing the search parameter L by 2'' is too strong: accessing the neighbor lists of two extra nodes is not the same as enlarging the candidate heap during the entire greedy search. A precise comparison would require measuring visited nodes and distance computations.
[Abstract and Section VI-B] The phrase ``does not sacrifices search efficiency'' should read ``does not sacrifice search efficiency''; also, the abstract's claim of the greatest improvement ``from 41.74% to 93.42%'' should identify the dataset and the specific base index to avoid overgeneralization.
[Figure 4 and Observation 1] The caption and text describe ``Rank of Local Optimum'' and ``20-NNs Overlap Rate,'' but the y-axis labels in Figure 4 are partially garbled. Please redraw the figures with readable axis labels and define the unit on the x-axis (the value of η) explicitly.
[Section VI-A, Datasets] The paper lists FACE as Inner Product distance, but the search algorithm in Algorithm 1 is described in terms of a generic distance function. Please clarify how the local-optimum test (closest point to the query) behaves under inner-product similarity, which is not a metric.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: conjugate-graph edges are extracted from search/construction logs and scored on held-out queries against true nearest-neighbor ground truth; the only self-citation is minor and non-load-bearing.

full rationale

The derivation chain is not circular. EnhanceGraph's conjugate graph is populated from two logs: pruned construction-log edges (Algorithm 4, G'[xb] = R - G[xb]) and routing edges extracted from historical or self-generated search logs (Algorithm 3). The added edges are then evaluated on test queries that are disjoint from the generated historical queries ('there is no test queries existing in the historical search queries'), and recall is measured against accurate NN ground truth (Definition 1), not against the conjugate graph's own labels. Thus the reported Recall@1 and Recall@10 improvements (e.g., 41.74% to 93.42% on GIST1M) are empirical outcomes, not values forced by construction. The one genuinely self-referential part is Algorithm 3 line 8, where x_g is defined as argmin over ANN_k(x_b) ∪ {x_b} rather than verified against true ground truth; the paper itself hedges this with 'In most cases (i.e., when the two cells are adjacent)'. That is a correctness/robustness caveat, not circularity, because the final evaluation uses external ground truth. Similarly, the text promises a theorem after Algorithm 3 but none appears; this is an omitted proof, not a circular step. The only self-citation found is reference [12] (SPANN), cited as an example of a disk-based index requiring IO; it is not load-bearing for any claim. No uniqueness theorem is imported from the authors, no fitted parameter is renamed as a prediction, and no known result is repackaged as new. The framework is benchmarked against external public datasets and an industrial dataset with real historical queries on FACE, so the central claim has independent empirical content.

Assumptions & free parameters 4 free parameters · 3 assumptions · 1 invented entities

The central claim rests on a data-driven heuristic: that learned local-to-global shortcut pairs generalize from training queries to unseen queries. The main free parameters are query-generation control (omega, k_g), the log search parameter L2, and the synthetic noise scale. The mostly unproven premise is the Voronoi adjacency and local homogeneity assumption used to assign global-optimum labels to generated queries. There are no fitted physical constants or new physical entities.

free parameters (4)

omega (generated query position parameter) = 0.51, 0.6, 0.7, 0.8, 0.9
Controls the distance of synthetic training queries from the base point along the edge to a k-NN. Smaller values are reported to identify more flaws on GIST1M, so the choice directly affects which local optima are discovered.
k_g (number of generated queries per base point) = 5
Set to 5 without a reported sensitivity study. It determines the size and coverage of the self-generated search log.
L2 (search list size used to generate logs) = 20, 40, 60, 80, 100
The conjugate graph mainly delivers routing improvement when the online search parameter L equals L2. This is a load-bearing choice because the paper shows a turning point in performance at L = L2.
historical search noise scale = U(-0.5*eta, 0.5*eta)
Synthetic historical search points for public datasets are generated by adding uniform noise scaled by the mean absolute vector value eta. The 0.5 scale is chosen without ablation and defines the training query distribution.

assumptions (3)

domain assumption Local optima of similar queries tend to coincide and to be k-NNs of the same global optimum (Observations 1-3).
This is the empirical basis for transferring edges learned on training queries to unseen test queries. It is validated only on two datasets (GIST1M and GLoVe-100) and is not guaranteed for arbitrary workloads.
ad hoc to paper Voronoi cells of a base point and its k-NNs are locally homogeneous and adjacent, so generated points near the perpendicular bisector lie in the base point's Voronoi cell.
Section IV-B uses this to label generated queries with a true global optimum. The paper only asserts this 'in most cases' and uses approximate k-NNs, so the true-nearest-neighbor label for synthetic queries is an unproven assumption.
domain assumption The full search log is collected with correct global optima for failure queries.
Section V.A states 'In our approach, we assume that the full search log is collected.' In production, global optima may require user feedback or asynchronous computation, so the assumption is strong.

invented entities (1)

Conjugate graph independent evidence
purpose: Stores routing edges (local optimum to global optimum) from search logs and non-routing pruned edges from the construction log. It is queried after the main graph search to improve Recall@1 and Recall@10.
It is an algorithmic data structure, not a physical entity, and its benefit is evidenced by recall and QPS experiments across multiple datasets, so a falsifiable experimental handle exists.

how reviews work

0 comments

Cite this review

Pith. "Pith review of EnhanceGraph: A Continuously Enhanced Graph-based Index for High-dimensional Approximate Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/PAPUXCE2

@misc{pith2026250613144,
  author       = {Pith},
  title        = {Pith review of: EnhanceGraph: A Continuously Enhanced Graph-based Index for High-dimensional Approximate Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PAPUXCE2}},
  note         = {Machine review of arXiv:2506.13144}
}

read the original abstract

Recently, Approximate Nearest Neighbor Search in high-dimensional vector spaces has garnered considerable attention due to the rapid advancement of deep learning techniques. We observed that a substantial amount of search and construction logs are generated throughout the lifespan of a graph-based index. However, these two types of valuable logs are not fully exploited due to the static nature of existing indexes. We present the EnhanceGraph framework, which integrates two types of logs into a novel structure called a conjugate graph. The conjugate graph is then used to improve search quality. Through theoretical analyses and observations of the limitations of graph-based indexes, we propose several optimization methods. For the search logs, the conjugate graph stores the edges from local optima to global optima to enhance routing to the nearest neighbor. For the construction logs, the conjugate graph stores the pruned edges from the proximity graph to enhance retrieving of k nearest neighbors. Our experimental results on several public and real-world industrial datasets show that EnhanceGraph significantly improves search accuracy with the greatest improvement on recall from 41.74% to 93.42%, but does not sacrifices search efficiency. In addition, our EnhanceGraph algorithm has been integrated into Ant Group's open-source vector library, VSAG.

Figures

Figures reproduced from arXiv: 2506.13144 by the authors.

**Figure 2.** Example of Searching on Proximity Graph. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** A Pipeline of the EnhanceGraph Framework. We utilize both search and construction log to construct a conjugate graph. A query [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (7 more)

**Figure 5.** Figure 5: Same Local Optimum Rate of Similar Point (Observation 3). [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]

**Figure 6.** Figure 6: Example of Generated Points in Voronoi Diagram. [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

**Figure 7.** Figure 7: Time-Accuracy Tradeoff (Varying Algorithms). [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]

**Figure 8.** Figure 8: Time-Accuracy Trade-off (Varying L1). [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]

**Figure 9.** Figure 9: Time-Accuracy Trade-off (Varying L2). ω ω ω ω ω ω ω ω ω ω [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]

**Figure 10.** Figure 10: Time-Accuracy Trade-off (Varying ω). only utilize the local optimum that is reached when searching for the list size L = L2 to connect to the global optimum. For L > L2, there’s a high possibility that the search process converges to a better local optimum, which migh…

**Figure 11.** Figure 11: Shot Rate on Different Queries (Varying ω) frequently than in VAMANA, due to the increased uncertainty in the search process caused by the hierarchical structure of HNSW. It’s because HNSW chooses different starting points in the bottom graph for each query, leading t…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 46 canonical work pages

[1]

Ongoing face recognition vendor test (frvt) part 2: Identification,

P. Grother, M. Ngan, and K. Hanaoka, “Ongoing face recognition vendor test (frvt) part 2: Identification,” 2018-11-27 2018

work page 2018
[2]

Full text search engine as scalable k-nearest neighbor recommendation system,

J. Suchal and P. N ´avrat, “Full text search engine as scalable k-nearest neighbor recommendation system,” inArtificial Intelligence in Theory and Practice III(M. Bramer, ed.), (Berlin, Heidelberg), pp. 165–173, Springer Berlin Heidelberg, 2010

work page 2010
[3]

High-throughput vector similarity search in knowledge graphs,

J. Mohoney, A. Pacaci, S. R. Chowdhury, A. Mousavi, I. F. Ilyas, U. F. Minhas, J. Pound, and T. Rekatsinas, “High-throughput vector similarity search in knowledge graphs,”Proc. ACM Manag. Data, vol. 1, jun 2023

work page 2023
[4]

The curse of dimensionality in data mining and time series prediction,

M. Verleysen and D. Franc ¸ois, “The curse of dimensionality in data mining and time series prediction,” inInternational work-conference on artificial neural networks, pp. 758–770, Springer, 2005

work page 2005
[5]

Approximate nearest neighbors: towards removing the curse of dimensionality,

P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality,” inProceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604–613, 1998

work page 1998
[6]

Fanng: Fast approximate nearest neighbour graphs,

B. Harwood and T. Drummond, “Fanng: Fast approximate nearest neighbour graphs,” inProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016

work page 2016
[7]

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

C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,”Proc. VLDB Endow., vol. 12, p. 461–474, jan 2019

work page 2019
[8]

Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters,

S. Gollapudi, N. Karia, V . Sivashankar, R. Krishnaswamy, N. Begwani, S. Raz, Y . Lin, Y . Zhang, N. Mahapatro, P. Srinivasan, A. Singh, and H. V . Simhadri, “Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters,” inProceedings of the ACM Web Conference 2023, WWW ’23, (New York, NY , USA), p. 3406–3416, Association for C...

work page 2023

Show all 50 references

[9]

Efficient and robust approxi- mate nearest neighbor search using hierarchical navigable small world graphs,

Y . A. Malkov and D. A. Yashunin, “Efficient and robust approxi- mate nearest neighbor search using hierarchical navigable small world graphs,”IEEE Transactions on Pattern Analysis and Machine Intelli- gence, vol. 42, no. 4, pp. 824–836, 2020

2020
[10]

An optimal algorithm for approximate nearest neighbor searching fixed dimensions,

S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y . Wu, “An optimal algorithm for approximate nearest neighbor searching fixed dimensions,”Journal of the ACM (JACM), vol. 45, no. 6, pp. 891–923, 1998

1998
[11]

Revisiting kd-tree for nearest neighbor search,

P. Ram and K. Sinha, “Revisiting kd-tree for nearest neighbor search,” inProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’19, (New York, NY , USA), p. 1378–1388, Association for Computing Machinery, 2019

2019
[12]

Spann: Highly-efficient billion-scale approximate nearest neighborhood search,

Q. Chen, B. Zhao, H. Wang, M. Li, C. Liu, Z. Li, M. Yang, and J. Wang, “Spann: Highly-efficient billion-scale approximate nearest neighborhood search,” inAdvances in Neural Information Processing Systems(M. Ranzato, A. Beygelzimer, Y . Dauphin, P. Liang, and J. W. Vaughan, eds...

2021
[13]

Multi- probe lsh: efficient indexing for high-dimensional similarity search,

Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li, “Multi- probe lsh: efficient indexing for high-dimensional similarity search,” in Proceedings of the 33rd international conference on Very large data bases, pp. 950–961, 2007

2007
[14]

A general and efficient querying method for learning to hash,

J. Li, X. Yan, J. Zhang, A. Xu, J. Cheng, J. Liu, K. K. W. Ng, and T.-c. Cheng, “A general and efficient querying method for learning to hash,” inProceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, (New York, NY , USA), p. 1333–1347, Association...

2018
[15]

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

X. Zhao, Y . Tian, K. Huang, B. Zheng, and X. Zhou, “Towards efficient index construction and approximate nearest neighbor search in high- dimensional spaces,”Proceedings of the VLDB Endowment, vol. 16, no. 8, pp. 1979–1991, 2023

1979
[16]

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

W. Li, Y . Zhang, Y . Sun, W. Wang, M. Li, W. Zhang, and X. Lin, “Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement,”IEEE Transactions on Knowledge and Data Engineering, vol. 32, no. 8, pp. 1475–1488, 2019

2019
[17]

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

M. Wang, X. Xu, Q. Yue, and Y . Wang, “A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,”Proc. VLDB Endow., vol. 14, p. 1964–1978, jul 2021

1964
[18]

Fast approximate nearest-neighbor search with k-nearest neighbor graph,

K. Hajebi, Y . Abbasi-Yadkori, H. Shahbazi, and H. Zhang, “Fast approximate nearest-neighbor search with k-nearest neighbor graph,” IJCAI’11, p. 1312–1317, AAAI Press, 2011

2011
[19]

Fast and accurate hashing via iterative nearest neighbors expansion,

Z. Jin, D. Zhang, Y . Hu, S. Lin, D. Cai, and X. He, “Fast and accurate hashing via iterative nearest neighbors expansion,”IEEE Transactions on Cybernetics, vol. 44, no. 11, pp. 2167–2177, 2014

2014
[20]

The relative neighbourhood graph of a finite planar set,

G. T. Toussaint, “The relative neighbourhood graph of a finite planar set,”Pattern Recognition, vol. 12, no. 4, pp. 261–268, 1980

1980
[21]

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

W. Li, Y . Zhang, Y . Sun, W. Wang, M. Li, W. Zhang, and X. Lin, “Approximate nearest neighbor search on high dimensional data — experiments, analyses, and improvement,”IEEE Transactions on Knowl- edge and Data Engineering, vol. 32, no. 8, pp. 1475–1488, 2020

2020
[22]

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

C. Fu, C. Wang, and D. Cai, “High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 8, pp. 4139–4150, 2022

2022
[23]

Diskann: Fast accurate billion-point nearest neighbor search on a single node,

S. Jayaram Subramanya, F. Devvrit, H. V . Simhadri, R. Krishnawamy, and R. Kadekodi, “Diskann: Fast accurate billion-point nearest neighbor search on a single node,” inAdvances in Neural Information Processing Systems(H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch ´e-Buc...

2019
[24]

Efficient approximate nearest neighbor search in multi-dimensional databases,

Y . Peng, B. Choi, T. N. Chan, J. Yang, and J. Xu, “Efficient approximate nearest neighbor search in multi-dimensional databases,”Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. 1–27, 2023

2023
[25]

High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations,

J. Gao and C. Long, “High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations,”Proc. ACM Manag. Data, vol. 1, jun 2023

2023
[26]

V oronoi diagrams and delaunay triangulations,

S. Fortune, “V oronoi diagrams and delaunay triangulations,” inHand- book of discrete and computational geometry, pp. 705–721, Chapman and Hall/CRC, 2017

2017
[27]

Two algorithms for constructing a delaunay triangulation,

D. Lee and B. Schachter, “Two algorithms for constructing a delaunay triangulation,”International Journal of Parallel Programming, vol. 9, pp. 219–242, 06 1980

1980
[28]

V oronoi diagrams—a survey of a fundamental ge- ometric data structure,

F. Aurenhammer, “V oronoi diagrams—a survey of a fundamental ge- ometric data structure,”ACM Comput. Surv., vol. 23, p. 345–405, sep 1991

1991
[29]

Locally homogeneous geometric manifolds,

W. M. Goldman, “Locally homogeneous geometric manifolds,” inPro- ceedings of the International Congress of Mathematicians 2010 (ICM

2010
[30]

Complaint-driven training data debugging for query 2.0,

W. Wu, L. Flokas, E. Wu, and J. Wang, “Complaint-driven training data debugging for query 2.0,” inProceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, (New York, NY , USA), p. 1317–1334, Association for Computing Machinery, 2020

2020
[31]

Understanding black-box predictions via influence functions,

P. W. Koh and P. Liang, “Understanding black-box predictions via influence functions,” inInternational conference on machine learning, pp. 1885–1894, PMLR, 2017

2017
[32]

Revisiting facial-recognition payment: Old problems still lingering,

L. Tang, “Revisiting facial-recognition payment: Old problems still lingering,”Nielsen Norman Group, vol. 20, 2022

2022
[33]

No card, no phone, no problem! alipay: Pay with your face, a balance between convenience, security and privacy,

B. W. G. Lines, “No card, no phone, no problem! alipay: Pay with your face, a balance between convenience, security and privacy,”Blog Writing Guide, 2020

2020
[34]

Retrieval- augmented generation for knowledge-intensive nlp tasks,

P. Lewis, E. Perez, A. Piktus, F. Petroni, V . Karpukhin, N. Goyal, H. K ¨uttler, M. Lewis, W.-t. Yih, T. Rockt ¨aschel,et al., “Retrieval- augmented generation for knowledge-intensive nlp tasks,”Advances in Neural Information Processing Systems, vol. 33, pp. 9459–9474, 2020

2020
[35]

[online] openai embedding docs

“[online] openai embedding docs.” https://openai.xiniushu.com/docs/ guides/embeddings, 2024

2024
[36]

[online] ann benchmarks

“[online] ann benchmarks.” https://github.com/erikbern/ ann-benchmarks, 2024

2024
[37]

Mathematical analysis of random noise,

S. O. Rice, “Mathematical analysis of random noise,”The Bell System Technical Journal, vol. 23, no. 3, pp. 282–332, 1944

1944
[38]

Robustness of classifiers: from adversarial to random noise,

A. Fawzi, S.-M. Moosavi-Dezfooli, and P. Frossard, “Robustness of classifiers: from adversarial to random noise,” inAdvances in Neural Information Processing Systems(D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, eds.), vol. 29, Curran Associates, Inc., 2016

2016
[39]

Approximate nearest neighbor queries in fixed dimensions.,

S. Arya and D. M. Mount, “Approximate nearest neighbor queries in fixed dimensions.,” inSODA, vol. 93, pp. 271–280, 1993

1993
[40]

Ood-diskann: Efficient and scalable graph anns for out-of-distribution queries,

S. Jaiswal, R. Krishnaswamy, A. Garg, H. V . Simhadri, and S. Agrawal, “Ood-diskann: Efficient and scalable graph anns for out-of-distribution queries,” 2022

2022
[41]

Qd-tree: Learning data layouts for big data analytics,

Z. Yang, B. Chandramouli, C. Wang, J. Gehrke, Y . Li, U. F. Minhas, P.-r. Larson, D. Kossmann, and R. Acharya, “Qd-tree: Learning data layouts for big data analytics,” SIGMOD ’20, (New York, NY , USA), p. 193–208, Association for Computing Machinery, 2020

2020
[42]

Sat: sampling acceleration tree for adaptive database repartition,

X. Xie, S. Shi, H. Wang, and M. Li, “Sat: sampling acceleration tree for adaptive database repartition,”World Wide Web, vol. 26, no. 5, pp. 3503– 3533, 2023

2023
[43]

Computing nearest-neighbor fields via propagation- assisted kd-trees,

K. He and J. Sun, “Computing nearest-neighbor fields via propagation- assisted kd-trees,” in2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 111–118, 2012

2012
[44]

Quicknn: Memory and per- formance optimization of k-d tree based nearest neighbor search for 3d point clouds,

R. Pinkham, S. Zeng, and Z. Zhang, “Quicknn: Memory and per- formance optimization of k-d tree based nearest neighbor search for 3d point clouds,” in2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 180–192, 2020

2020
[45]

Practical and optimal lsh for angular distance,

A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, and L. Schmidt, “Practical and optimal lsh for angular distance,”Advances in neural information processing systems, vol. 28, 2015

2015
[46]

Approximate nearest neighbor search by residual vector quantization,

Y . Chen, T. Guan, and C. Wang, “Approximate nearest neighbor search by residual vector quantization,”Sensors, vol. 10, no. 12, pp. 11259– 11273, 2010

2010
[47]

The curse of dimensionality,

M. K ¨oppen, “The curse of dimensionality,” in5th online world con- ference on soft computing in industrial applications (WSC5), vol. 1, pp. 4–8, 2000

2000
[48]

Product quantization for nearest neighbor search,

H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,”IEEE transactions on pattern analysis and machine intelligence, vol. 33, no. 1, pp. 117–128, 2010

2010
[49]

Optimized product quantization for approximate nearest neighbor search,

T. Ge, K. He, Q. Ke, and J. Sun, “Optimized product quantization for approximate nearest neighbor search,” inProceedings of the IEEE conference on computer vision and pattern recognition, pp. 2946–2953, 2013

2013
[2010]

I: Plenary Lectures and Ceremonies Vols

(In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures, pp. 717–744, World Scientific, 2010

2010

Pith tools

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

[1] [1]

Ongoing face recognition vendor test (frvt) part 2: Identification,

P. Grother, M. Ngan, and K. Hanaoka, “Ongoing face recognition vendor test (frvt) part 2: Identification,” 2018-11-27 2018

work page 2018

[2] [2]

Full text search engine as scalable k-nearest neighbor recommendation system,

J. Suchal and P. N ´avrat, “Full text search engine as scalable k-nearest neighbor recommendation system,” inArtificial Intelligence in Theory and Practice III(M. Bramer, ed.), (Berlin, Heidelberg), pp. 165–173, Springer Berlin Heidelberg, 2010

work page 2010

[3] [3]

High-throughput vector similarity search in knowledge graphs,

J. Mohoney, A. Pacaci, S. R. Chowdhury, A. Mousavi, I. F. Ilyas, U. F. Minhas, J. Pound, and T. Rekatsinas, “High-throughput vector similarity search in knowledge graphs,”Proc. ACM Manag. Data, vol. 1, jun 2023

work page 2023

[4] [4]

The curse of dimensionality in data mining and time series prediction,

M. Verleysen and D. Franc ¸ois, “The curse of dimensionality in data mining and time series prediction,” inInternational work-conference on artificial neural networks, pp. 758–770, Springer, 2005

work page 2005

[5] [5]

Approximate nearest neighbors: towards removing the curse of dimensionality,

P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality,” inProceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604–613, 1998

work page 1998

[6] [6]

Fanng: Fast approximate nearest neighbour graphs,

B. Harwood and T. Drummond, “Fanng: Fast approximate nearest neighbour graphs,” inProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016

work page 2016

[7] [7]

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

C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,”Proc. VLDB Endow., vol. 12, p. 461–474, jan 2019

work page 2019

[8] [8]

Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters,

S. Gollapudi, N. Karia, V . Sivashankar, R. Krishnaswamy, N. Begwani, S. Raz, Y . Lin, Y . Zhang, N. Mahapatro, P. Srinivasan, A. Singh, and H. V . Simhadri, “Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters,” inProceedings of the ACM Web Conference 2023, WWW ’23, (New York, NY , USA), p. 3406–3416, Association for C...

work page 2023