Pith. sign in

REVIEW 4 major objections 5 minor 47 references

HENN: A Hierarchical Epsilon Net Navigation Graph for 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 ↗

Pith's one-line read Building hierarchical ANN layers as epsilon-nets guarantees polylogarithmic worst-case query time while keeping HNSW-like practical speed.

desk verdict HENN's epsilon-net layering idea is promising and the experiments are encouraging, but the central polylog worst-case guarantee is not proven as stated, and the implementation does not instantiate the structure the theory requires. read the letter →

arxiv 2505.17368 v1 pith:EC62QQ6J submitted 2025-05-23 cs.DS

Mohsen Dehghankar , Abolfazl Asudeh This is my paper · ORCID
classification cs.DS
keywords approximatenearestneighborsearchepsilon-netshierarchicalgraphindexHNSWworst-casequerytimepolylogarithmicboundnavigablegraphsringranges
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 sets out to close a long-standing gap in approximate nearest neighbor search: methods like HNSW are fast in practice but have no worst-case query-time guarantee and can degrade to linear time on adversarial data, while structures with proven guarantees such as cover trees and navigating nets are difficult to implement and scale poorly. HENN attacks this gap by replacing HNSW's random layer assignment with layers that are explicitly constructed as $\varepsilon$-nets, so each layer hits every 'heavy' ring range of the layer below it. The authors claim this yields a worst-case query time of $O(d \cdot d^* \cdot \rho_\delta \cdot \log^2 n)$, polylogarithmic in the dataset size $n$ and independent of the data distribution, while keeping the index linear in $n$ and the implementation close to HNSW. They also argue that HNSW's randomly sampled layers form $\varepsilon$-nets with high probability, which would explain its empirical success within the same framework. If these claims hold, HENN would offer the reliability of theoretically grounded hierarchies at the practical cost and simplicity of modern graph-based ANN indexes.

What carries the argument

The machine that does the work is the $\varepsilon$-net for ring ranges. A ring range is the set of points whose distance from a base point lies between $r_1$ and $r_2$; the family has VC-dimension $\Theta(d)$, so a random sample of size $O((d/\varepsilon)\log(d/\varepsilon))$ intersects every ring containing more than an $\varepsilon$ fraction of the points. By choosing $\varepsilon(s)$ as above, each net is small enough to shrink the layer by $2^m$, and the ring-space guarantee lets Lemma 3 convert the greedy search's output in one layer into a bound on how many lower-layer points can lie between the query and that output. The second parameter is $\rho_\delta$, the navigation graph's recall bound, defined as the smallest $k$ such that greedy search on that layer returns a point among the true $k$ nearest neighbors with probability at least $\delta$; it enters the query-time bound as a multiplicative factor.

What would settle it

Take a small synthetic point set, build HENN with the paper's implementation, and exhaustively enumerate every ring range that contains more than $\epsilon |L_i|$ points; if any such heavy range is missed by layer $L_{i+1}$, the premise of Theorem 4 is observably false for that index. A complementary check is to measure worst-case query hops on adversarial exponential data as $n$ grows: if the maximum hop count or runtime departs from the polylogarithmic trend and approaches linear growth, the claimed data-independent guarantee is not what the implementation delivers.

Watch

Extended reading notes

Core claim

The central discovery is that the hierarchy, not the navigable graph, is what carries the worst-case guarantee. HENN builds layer $L_{i+1}$ as an $\varepsilon$-net of $L_i$ with respect to ring ranges, using $\varepsilon(s) = c_0 d \log s / (s 2^m)$; the net property forces the layer size to shrink by a factor $2^m$ each step, giving $O(\log n)$ layers and index size $O(n)$. Querying descends greedily from the root layer; Lemma 3 bounds the number of points closer to the query than the returned point by $\varepsilon \cdot (\rho_\delta+2) \cdot n$, and an induction over layers yields Theorem 4: query time $O(d \cdot d^* \cdot \rho_\delta \cdot \log^2 n)$. A corollary states that HNSW enjoys the same polylogarithmic bound whenever its random layers are $\varepsilon$-nets with high probability, and HENN makes that property explicit rather than accidental.

Load-bearing premise

The guarantee stands or falls on whether every layer is really an epsilon-net of the previous layer, because the implementation checks the property only against a random handful of ring ranges, not all of them; if some heavy ring is missed, the layer can be much sparser than the theory requires and the polylogarithmic bound no longer follows.

Editorial extensions

If this is right

  • If Theorem 4 holds, ANN query time is $O(d \cdot d^* \cdot \rho_\delta \cdot \log^2 n)$ in the worst case, so for constant degree and recall-bound graphs the cost stays polylogarithmic no matter how skewed the data is.
  • The index remains linear in $n$, matching HNSW's memory footprint, so the guarantee is bought with indexing time, not space.
  • HNSW itself inherits a probabilistic polylogarithmic bound if its randomly sampled layers are $\varepsilon$-nets with high probability, giving a theoretical explanation for its practical speed.
  • Because the navigable graph is a black box, any existing graph ANN method (kNN graph, NSW, or a Delaunay-style graph) can be wrapped by HENN and receive the same worst-case layer guarantees.
  • On skewed synthetic data HENN reports fewer greedy hops and faster queries than HNSW, with the gap widening as skewness and dataset size grow.

Reading between the lines

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

  • Editorial inference: the proof's use of $\rho_\delta$ (returning at least one of the top-$k$ points) suggests a natural generalization to standard recall@$k$, where returning $k$ points would multiply the bound by $k$ or by a per-level candidate-set size; the paper does not develop this.
  • Editorial inference: the dependence on explicit $\varepsilon$-net verification suggests a practical tuning knob: checking more sampled ring ranges tightens the gap between the implemented index and the theorem's assumption, and an adaptive verifier could trade indexing time for a probabilistic certificate of the net property.
  • Editorial inference: because the guarantee relies on bounded VC-dimension of ring ranges, HENN's data-independent bound should transfer to any metric with $\Theta(d)$ VC-ring-dimension, but not to learned or implicit metrics where that dimension is uncontrolled; testing this boundary would be a clean stress test.
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

4 major / 5 minor

Summary. The paper proposes HENN, a hierarchical ANN index in which each layer is an ε-net of the previous layer with respect to ring ranges, and a query is answered by greedy descent from the root layer to the base point set. The central theoretical claim is Theorem 4, stating that the query time is O(d·d*·ρδ·log²n) in the worst case, independent of the data distribution, where d* is the average degree of the navigable graph and ρδ is the Recall Bound of that graph. A corollary claims a probabilistic polylogarithmic query-time bound for HNSW under the assumption that HNSW layers form ε-nets. The paper includes experiments on SIFT, GloVe, MNIST, and synthetic skewed data, reporting query-time speedups over HNSW on the synthetic data and comparable performance on standard benchmarks.

Significance. If the worst-case guarantee of Theorem 4 were established, the paper would offer a practically relevant modular ANN structure that combines a provable polylogarithmic query bound with an implementation close to HNSW. The construction idea—using ε-nets of ring ranges to obtain coverage guarantees at every layer—is natural and, in principle, promising. The paper is clearly written, and the experimental comparison is transparent about index-size and indexing-time trade-offs. The stated result would also provide a step toward theoretical understanding of HNSW. However, the correctness of the main theorem is not established: the proof converts a per-layer probabilistic statement into a deterministic worst-case bound without the necessary amplification, and it applies a Recall Bound condition to starting-node distributions that do not match the query algorithm. These gaps are load-bearing for the paper's central claim.

major comments (4)
  1. [Theorem 4 and Appendix E.3] The claimed deterministic worst-case bound is not supported by the proof. Lemma 3 gives a bound that holds only with probability more than δ, for a single layer transition. The proof of Theorem 4 applies Lemma 3 at each layer but never amplifies or union-bounds over the L = O(log n) layers. If the event fails at any layer, the starting point for the bottom layer may be far from q, and the greedy search can then visit Θ(n) points; the failure probability δ^L can be small (e.g., with δ = 0.9 and m = 1, δ^L ≈ 0.12 for n = 2^20). Thus the proof does not establish the advertised worst-case bound, nor does it establish a meaningful expected-time bound without additional assumptions on failure costs.
  2. [Definition 3 and §2.2] Definition 3 defines ρδ with probability taken over all possible initial nodes of the navigable graph, presumably under a uniform distribution over nodes. However, Query(H,q) (Algorithm 4) starts the search at each lower layer from the point returned by the greedy search in the layer above. That induced starting distribution is not uniform and may depend on the query point. Lemma 3 therefore does not apply to the actual recursive search unless the authors prove that the Recall Bound condition holds for the particular starting distribution produced by the upper layers; no such argument appears in Section 3 or Appendix E.
  3. [Corollary 3, §3.1] The claimed HNSW guarantee is conditional on an unproved assumption. The corollary states that HNSW achieves polylogarithmic query time 'assuming that each layer forms an ε-net with a specific probability,' but the paper does not prove that the layers constructed by HNSW satisfy this ε-net property. Since HNSW assigns levels by random sampling independently of the geometry of ring ranges, the assumption is effectively the entire content of the HNSW claim. The abstract's statement that the paper 'establishes a probabilistic polylogarithmic query time bound for HNSW' is therefore not justified by the presented results.
  4. [Appendix G.2] The implemented ε-net verification is a heuristic that checks only r randomly selected ring ranges rather than all heavy ranges. The paper does not specify the value of r, the sampling distribution over ranges, or a failure analysis. Consequently, the index used in the experiments may not satisfy the ε-net property on which Lemma 3 and Theorem 4 rely. The experiments therefore do not test the data structure whose theoretical guarantees are proved, and the practical claims about worst-case behavior are not supported by the evaluation.
minor comments (5)
  1. [Equation (1) and throughout] The notation '2m' is ambiguous: it appears to mean 2^m in Lemma 2, in the proof of Theorem 4, and in the statement that the value is 'less than 64 in HNSW,' but the exponent is not rendered consistently. Please use proper superscripts throughout to avoid confusion.
  2. [Appendix E.3] The cost of the bottom-layer search is written as O(d·log n·2^m·ρδ·d*), but substituting ε from Equation (1) into ε·n gives O(d·log n·ρδ·d*/2^m). The factor is off by (2^m)^2; while this does not change the polylogarithmic order, the derivation should be corrected.
  3. [Definition 1] Definition 1 states that each node represents a point in X, but the same point may appear in multiple layers of the hierarchy. Please clarify how duplicate representations are handled (e.g., whether separate nodes are instantiated per layer) and how the inter-layer edges are maintained.
  4. [Section 3, paragraph before §3.1] The statement 'for most of the existing navigable graphs [30, 29], ρ0.9 = O(1)' is not substantiated; Figure 11 reports values for specific graphs and settings, but not for all graphs discussed. A citation or a more careful qualifier is needed.
  5. [Appendix G.2] The text says 'Additional implementation details for this phase are provided in the supplemental material' while the appendix is itself part of the paper's supplemental material; the relevant details (range sampling procedure, value of r, acceptance criterion) should be stated directly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 4 is derived from the external ε-net theorem with explicit inputs (ε-net layers, recall bound ρδ, degree d*), the paper contains no self-citations, and the flagged HNSW claim is an explicitly conditional statement rather than a reduction by construction.

full rationale

The derivation chain claimed by the paper is self-contained and does not reduce to its own inputs. Theorem 4's bound O(d·d*·ρδ·log² n) is obtained by combining (i) the ring-range ε-net property enforced in Algorithm 1 and justified by the external ε-net theorem (Theorem 5, cited to Har-Peled/Indyk/Motwani and Haussler/Welzl), (ii) the Recall Bound ρδ (Definition 3), an explicit accuracy parameter of the navigable graph, and (iii) the recursion T(n) ≤ T(n/2^m) + O(d·2^m·log n·ρδ·d*) solved by the Master Theorem (Appendix E.3). No equation defines the query-time conclusion in terms of itself, and no fitted parameter is renamed as a prediction; ρδ is stated as an input parameter, and the bound degrades as ρδ grows. The paper contains no self-citations, so no load-bearing self-citation chain exists. Genuine weaknesses exist, but they are correctness and evidence gaps, not circular reductions, and per the hard rules they must not be scored as circularity: (a) Corollary 3's HNSW claim is explicitly conditional ('assuming that each layer forms an ε-net with a specific probability'), and the paper never checks that HNSW's geometric level assignment satisfies the ε-net theorem's sample-size requirement, so the HNSW explanation rests on an unverified premise that the introduction asserts as shown; (b) Theorem 4's proof applies Lemma 3 'inductively' without amplifying the per-layer success probability δ over L = O(log n) layers, and Definition 3's probability is over uniformly random starting nodes whereas lower-layer searches start from the previous layer's output, so the stated deterministic worst-case bound is not established; (c) Appendix G.2 verifies the ε-net property only against r randomly sampled ring ranges, so the implemented index may not satisfy the theorem's premise and the experiments do not independently confirm the guarantee; (d) the abstract's 'independent of the input data distribution' overstates a bound that depends on ρδ, which the paper's own Figure 11 shows grows with data skewness. These are unverified assumptions and proof gaps to weigh under correctness risk, not equivalence-by-construction, so the circularity score is 0.

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

The core derivation relies on the ε-net theorem for ring ranges; the main free parameters are the layer decay m, the proof constant c0, and the verification-range count r, none of which are fixed by the theory. The practical implementation weakens the ε-net requirement to a sampled check, which is the most important gap between theory and practice.

free parameters (4)
  • m (layer decay factor) = not specified; set to match HNSW baseline
    Hyperparameter controlling the exponential decay of layer sizes in Equation 1; chosen by the user and affects the constant in the query time bound.
  • c0 (epsilon-net constant) = not numeric; 'sufficiently large constant'
    Introduced in Equation 1 to force layer sizes to shrink by a factor 2^m; no concrete value is given, so the construction is not fully specified.
  • r (number of verification ranges) = not reported
    Implementation hyperparameter in Appendix G.2: the ε-net check samples only r random ring ranges instead of all ranges, so the 'ε-net' property is only enforced approximately.
  • phi (sampling failure probability) = 1/2
    Set to 1/2 in the sampling-based ε-net construction; affects the expected number of sampling repetitions and is an arbitrary constant.
assumptions (4)
  • domain assumption The ring range space (X, R) has VC-dimension Θ(d).
    Proposition 1 derives this from the assumed Θ(d) VC-dimension of the distance function; used to invoke the ε-net theorem. Holds for ℓp and angular distances, but not for unbounded VC-dimension.
  • standard math A random sample of size O((d/ε) log(d/ε) + (1/ε) log(1/φ)) is an ε-net with probability at least 1-φ (ε-net Theorem).
    Used in Theorem 5 and throughout the construction; standard result for range spaces with finite VC-dimension, cited from [12, 13].
  • domain assumption The navigable graph used in each layer has constant average degree d* and constant recall bound ρδ.
    Theorem 4's polylog bound is linear in d* and ρδ; the paper asserts these are O(1) for practical graphs like NSW, but proves no such statement.
  • ad hoc to paper Each layer constructed is a true ε-net of its predecessor with respect to all ring ranges.
    The theoretical analysis assumes BuildEpsNet returns an ε-net. The implementation instead checks a random sample of r ranges, so this premise is not guaranteed by the shipped algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/EC62QQ6J

@misc{pith2026250517368,
  author       = {Pith},
  title        = {Pith review of: HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EC62QQ6J}},
  note         = {Machine review of arXiv:2505.17368}
}
abstract

Hierarchical graph-based algorithms such as HNSW have achieved state-of-the-art performance for Approximate Nearest Neighbor (ANN) search in practice, yet they often lack theoretical guarantees on query time or recall due to their heavy use of randomized heuristic constructions. Conversely, existing theoretically grounded structures are typically difficult to implement and struggle to scale in real-world scenarios. We propose the Hierarchical $\varepsilon$-Net Navigation Graph (HENN), a novel graph-based indexing structure for ANN search that combines strong theoretical guarantees with practical efficiency. Built upon the theory of $\varepsilon$-nets, HENN guarantees polylogarithmic worst-case query time while preserving high recall and incurring minimal implementation overhead. Moreover, we establish a probabilistic polylogarithmic query time bound for HNSW, providing theoretical insight into its empirical success. In contrast to these prior hierarchical methods that may degrade to linear query time under adversarial data, HENN maintains provable performance independent of the input data distribution. Empirical evaluations demonstrate that HENN achieves faster query time while maintaining competitive recall on diverse data distributions, including adversarial inputs. These results underscore the effectiveness of HENN as a robust and scalable solution for fast and accurate nearest neighbor search.

Figures

Figures reproduced from arXiv: 2505.17368 by the authors.

Figure 1
Figure 1. A simple representation of the Hierarchical [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Query speed vs. Recall@10 - up and to the right is better (higher AUC). HENN performs at [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. d = 16 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (5 more)
Figure 6
Figure 6. Figure 6: d = 16 [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 9
Figure 9. Figure 9: Query speed vs Recall@10 - up and to the right is better (higher AUC). The input is an [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 10
Figure 10. Figure 10: Visualization of Lemma 3. In this example, [PITH_FULL_IMAGE:figures/full_fig_p018_10.png]
Figure 11
Figure 11. Figure 11: Comparing Recall Bound ρδ for different navigation graphs. Average Hits is the fraction of times that at least one point is retrieved within the k nearest points. The red dotted lines show the threshold for δ = 0.9. The intersection of the red dotted line with the plo…
Figure 12
Figure 12. Figure 12: Comparing the Recall@k for different values of k on HENN structure integrated with different [PITH_FULL_IMAGE:figures/full_fig_p022_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 34 canonical work pages

  1. [1]

    Ann-benchmarks: A bench- marking tool for approximate nearest neighbor algorithms

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A bench- marking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020

    work page 2020

  2. [2]

    Multidimensional binary search trees used for associative searching

    Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Com- munications of the ACM, 18(9):509–517, 1975

    work page 1975

  3. [3]

    Cover trees for nearest neighbor

    Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning, pages 97–104, 2006

    work page 2006

  4. [4]

    The Discrepancy Method: Randomness and Complexity

    Bernard Chazelle. The Discrepancy Method: Randomness and Complexity . Cambridge University Press, Cambridge, UK, 2000

    2000

  5. [5]

    Locality-sensitive hashing scheme based on p-stable distributions

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 253–262, 2004

    work page 2004

  6. [6]

    Computational Geometry: Algorithms and Applications

    Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Heidelberg, 3rd edition, 2008

    work page 2008

  7. [7]

    A survey on rag meeting llms: Towards retrieval-augmented large language models

    Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. A survey on rag meeting llms: Towards retrieval-augmented large language models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 6491–6501, 2024

    2024

  8. [8]

    Optimized product quantization

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence, 36(4):744–755, 2013

    work page 2013

Show all 47 references
  1. [9]

    Fast incremental maintenance of approximate histograms

    Phillip B Gibbons, Yossi Matias, and Viswanath Poosala. Fast incremental maintenance of approximate histograms. ACM Transactions on Database Systems (TODS), 27(3):261–298, 2002

    2002

  2. [10]

    A comprehensive survey on vector database: Storage and retrieval technique, challenge

    Yikun Han, Chunjiang Liu, and Pengfei Wang. A comprehensive survey on vector database: Storage and retrieval technique, challenge. arXiv preprint arXiv:2310.11703, 2023

    2023

  3. [11]

    Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs

    Sariel Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2011

    2011

  4. [12]

    Approximate nearest neighbor: Towards removing the curse of dimensionality

    Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. 2012

    2012

  5. [13]

    Epsilon-nets and simplex range queries

    David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. In Proceedings of the second annual symposium on Computational geometry, pages 61–71, 1986

    1986

  6. [14]

    Uniform manifold approximation and projection

    John Healy and Leland McInnes. Uniform manifold approximation and projection. Nature Reviews Methods Primers, 4(1):82, 2024

    2024

  7. [15]

    Approximate nearest neighbors: towards removing the curse of dimensionality

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

    1998

  8. [16]

    Worst-case performance of popular approximate nearest neigh- bor search implementations: Guarantees and limitations

    Piotr Indyk and Haike Xu. Worst-case performance of popular approximate nearest neigh- bor search implementations: Guarantees and limitations. Advances in Neural Information Processing Systems, 36:66239–66256, 2023

    2023

  9. [17]

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

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems, 32, 2019

    2019

  10. [18]

    Product quantization for nearest neighbor search

    Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117–128, 2010. 10

    2010

  11. [19]

    Product quantization for nearest neighbor search

    Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), volume 33, pages 117–128. IEEE, 2011

    2011

  12. [20]

    When large language models meet vector databases: A survey

    Zhi Jing, Yongye Su, Yikun Han, Bo Yuan, Haiyun Xu, Chunjiang Liu, Kehai Chen, and Min Zhang. When large language models meet vector databases: A survey. arXiv preprint arXiv:2402.01763, 2024

    2024 arXiv

  13. [21]

    Extensions of lipschitz mappings into a hilbert space

    William B Johnson, Joram Lindenstrauss, et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984

    1984

  14. [22]

    Navigating nets: Simple algorithms for proximity search

    Robert Krauthgamer and James R Lee. Navigating nets: Simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 798–807. Citeseer, 2004

    2004

  15. [23]

    Correlations in topological models of 2d random cellular structures

    Gérard Le Caer and Renaud Delannay. Correlations in topological models of 2d random cellular structures. Journal of Physics A: Mathematical and General, 26(16):3931, 1993

    1993

  16. [24]

    Gradient-based learning applied to document recognition

    Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998

    1998

  17. [25]

    Retrieval-augmented generation for knowledge-intensive nlp tasks

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in neural information processing systems...

    2020

  18. [26]

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

    Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering , 32(8):1475–1488, 2019

    2019

  19. [27]

    Revisiting k-nearest neighbor graph construction on high-dimensional data: Experiments and analyses

    Yingfan Liu, Cheng Hong, and Jiangtao Jiang. Revisiting k-nearest neighbor graph construction on high-dimensional data: Experiments and analyses. arXiv preprint arXiv:2112.02234, 2021

    2021 arXiv

  20. [28]

    Hvs: hierarchical graph struc- ture based on voronoi diagrams for solving approximate nearest neighbor search

    Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. Hvs: hierarchical graph struc- ture based on voronoi diagrams for solving approximate nearest neighbor search. Proceedings of the VLDB Endowment, 15(2):246–258, 2021

    2021

  21. [29]

    Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs

    Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824–836, 2018

    2018

  22. [30]

    Approximate nearest neighbor algorithm based on navigable small world graphs

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61–68, 2014

    2014

  23. [31]

    Hierar- chical clustering-based graphs for large scale approximate nearest neighbor search

    Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. Hierar- chical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition, 96:106970, 2019

    2019

  24. [32]

    Five balltree construction algorithms

    Stephen M Omohundro. Five balltree construction algorithms. 1989

    1989

  25. [33]

    Competitive quantization for ap- proximate nearest neighbor search

    Ezgi Can Ozan, Serkan Kiranyaz, and Moncef Gabbouj. Competitive quantization for ap- proximate nearest neighbor search. IEEE Transactions on Knowledge and Data Engineering, 28(11):2884–2894, 2016

    2016

  26. [34]

    Survey of vector database management systems

    James Jie Pan, Jianguo Wang, and Guoliang Li. Survey of vector database management systems. The VLDB Journal, 33(5):1591–1615, 2024

    2024

  27. [35]

    Glove: Global vectors for word representation

    Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543. Association for Computational Linguistics, 2014. 11

    2014

  28. [36]

    Falconn++: A locality-sensitive filtering approach for approximate nearest neighbor search

    Ninh Pham and Tao Liu. Falconn++: A locality-sensitive filtering approach for approximate nearest neighbor search. Advances in Neural Information Processing Systems, 35:31186–31198, 2022

    2022

  29. [37]

    Graph-based nearest neighbor search: From practice to theory

    Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning, pages 7803–7813. PMLR, 2020

    2020

  30. [38]

    Visualizing data using t-sne

    Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008

    2008

  31. [39]

    Random sampling with a reservoir

    Jeffrey S Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37–57, 1985

    1985

  32. [40]

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

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631, 2021. 12 Appendix Table of Content

    2021 arXiv

  33. [41]

    Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A

  34. [42]

    ε-Net and Navigable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B

  35. [43]

    Dynamic Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C

  36. [44]

    Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D

  37. [45]

    Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E

  38. [46]

    Pseudo-codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F

  39. [47]

    G A Related Work In this section, we review the literature most relevant to our work

    More on Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G A Related Work In this section, we review the literature most relevant to our work. A broader overview of techniques for the Appr...

Pith tools

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