Pith. sign in

REVIEW 3 major objections 6 minor 47 references

An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval

T0 review · 3 major / 6 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a continuously refined even-regular graph, crEG, achieves up to 250% higher search throughput than state-of-the-art proximity graphs at 99% recall, while its unrefined version is 2–3 times faster to construct and both

desk verdict A solid incremental ANNS paper with real contributions, but the 'connectivity at any time' guarantee is contradicted by the paper's own algorithm. read the letter →

arxiv 2607.27623 v1 pith:CYQKIKTO submitted 2026-07-30 cs.IR

Nico Hezel , Kai Uwe Barthel , Konstantin Schall , Klaus Jung This is my paper · ORCID
classification cs.IR
keywords approximatenearestneighborsearchproximitygrapheven-regularexploratorycontinuousedgeoptimizationaveragedistancemultimediaretrievalconstruction
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

Approximate nearest neighbor search underpins multimedia retrieval, but graph-based indexes are often slow to build and are evaluated only for query points outside the database. The authors propose crEG, an even-regular undirected graph that is constructed incrementally and can be continuously refined by swapping edges while serving searches. They show that this design leads to state-of-the-art search speed, especially on high-dimensional datasets, with dramatically lower construction time. They also introduce a protocol for 'exploratory search' where the query is an indexed item, and show that crEG is up to 50% more efficient there, a setting in which ordinary ANNS effectiveness does not translate directly.

What carries the argument

The central objects are the even-regular undirected graph (every vertex has exactly d neighbors, d even) and the Average Neighbor Distance δN, a metric that sums the distances from each vertex to its neighbors. Because swapping endpoints of two edges only changes δN by comparing sums of edge weights, δN offers a cheap, locally sensitive signal for deciding which edges to replace—unlike graph quality, which is insensitive to such small changes. Construction and optimization both consist of carefully orchestrated edge removals and additions that preserve even regularity and, the authors argue, connectivity. The even degree also guarantees an Eulerian cycle, giving every vertex two edge-disjoin

What would settle it

Instrument Algorithm 4 while running on SIFT1M or GloVe: during each optimization iteration, immediately after Step (3) of an edge swap, issue a range search from a random vertex to a random target and check whether the search can reach the target within a fixed hop budget. If even a small percentage of such concurrent searches fail to complete, the 'guarantee graph connectivity at any time' claim is false. Separately, re-running the GloVe experiment with concurrent edge optimization and without it should show crEG still beats HNSW by 250% at recall@100=0.99; if the gap shrinks substantially u

Watch

Extended reading notes

Core claim

crEG maintains a fixed even degree per vertex, which makes the graph Eulerian and 2-edge-connected, and guides all edge changes by a new metric, the Average Neighbor Distance (δN), that is sensitive to small local swaps. New vertices are added by performing a range search and replacing d/2 existing edges with d new ones, in a way that approximates a Monotonic Relative Neighborhood Graph. A separate continuous edge-optimization routine can then iteratively improve the graph in the background, reducing δN and increasing search efficiency. Experiments show that the unoptimized EG builds 2–3 times faster than HNSW, NSG, and SSG while remaining competitive, and that the optimized crEG reaches up

Load-bearing premise

The load-bearing premise is that the continuous edge-optimization algorithm can operate in the background without hurting user searches, which requires that the graph remains navigable at every intermediate step; the paper acknowledges transient states where two vertices may become unreachable, but never measures how often or for how long those states occur.

Editorial extensions

If this is right

  • If the construction-time claim holds, multimedia indexes can be built incrementally in near real time; the paper estimates that adding a vertex to a billion-point SIFT index would take roughly 6.6 ms on the test hardware.
  • The 250% search-speed gain at 99% recall on high-dimensional embeddings would make high-accuracy ANNS practical in latency-sensitive production systems, where recall targets of 0.99 are often considered too expensive.
  • The exploratory-search protocol, treating indexed items as queries with the query vertex as the seed, could become a standard evaluation for recommendation-style browsing, revealing behavior that standard ANNS benchmarks miss.
  • The continuous edge-optimization algorithm is designed to run in parallel with user queries, so an index could improve over time without downtime, effectively self-tuning the graph as it serves traffic.
  • The even-regularity and connectivity properties are prerequisites for future dynamic ops, specifically vertex deletion, which the paper identifies as open future work.

Reading between the lines

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

  • The Average Neighbor Distance metric, because it is locally computable from edge weights, could be adopted by other graph-construction methods as a cheaper substitute for graph quality, independent of the rest of crEG.
  • The paper's finding that standard ANNS efficiency does not transfer to exploratory search suggests that production systems with item-based recommendations should benchmark with seeded queries; one can test this hypothesis by running the same protocol on other graph families not in the original comparison.
  • The connectivity-at-any-time claim is the weakest link: Algorithm 4 explicitly states that vertices {vB, vC} 'may become unreachable' during a swap. A testable extension would instrument the optimization loop and count transient disconnections, then measure whether concurrent searches ever fail during that window.
  • The stated complexity O(n^{1/9} log n) for search and insertion is derived empirically on SIFT-like data; an obvious stress test is to repeat the scalability experiment on datasets with higher local intrinsic dimension (e.g., LID > 25), where the constants could degrade the predicted 6.6 ms insertion time.
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 / 6 minor

Summary. The paper proposes crEG, an even-regular undirected proximity graph for approximate nearest-neighbor search (ANNS) and exploratory search. Construction is incremental: a new vertex is attached by removing existing edges and connecting it to neighbors found by range search, while an optional edge-optimization stage swaps edge endpoints to reduce the average neighbor distance δN. The authors claim that both manipulation algorithms preserve connectivity at all times, that the unoptimized graph (EG) is 2–3 times faster to construct than current state-of-the-art graphs, and that the optimized graph (crEG) achieves up to 250% higher QPS at recall@100=0.99 on GloVe, with additional gains in an exploratory-search protocol. Experiments compare against HNSW, NSG, NSSG, kGraph, EFANNA, DPG, and ONNG on Audio, SIFT1M, Deep1M, and GloVe.

Significance. If the results hold, the paper offers a useful construction-speed/search-speed trade-off for graph-based ANNS, and its exploration protocol is a valuable addition to the evaluation toolkit. The method is simple and does not require a hierarchical structure or a separate VP-tree, and the paper includes ablation studies (e.g., random graph plus edge optimization) that isolate the contribution of the proposed components. However, the two headline theoretical contributions—connectivity at any time and the ability to run edge optimization in parallel with live user queries—are undermined by the algorithm's own statements, and the empirical scalability claim is presented as a complexity result without a derivation. The performance comparisons also lack variance estimates and full hyperparameter disclosure.

major comments (3)
  1. [§3.3, Algorithm 4, Step (3)] The abstract and §3.1 claim both manipulation algorithms 'guarantee graph connectivity at any time,' and §3.3 states the optimizer 'can still operate in parallel with regular user search queries in a production system.' Yet Algorithm 4, Step (3) explicitly states: 'The vertices {vB, vC} may become unreachable for vA and vD.' Step (4) is only an attempt to restore connectivity, and Step (6) reverts changes only after several iterations. Thus the graph is not guaranteed connected during the optimization process. The manuscript neither quantifies the disconnection window nor proves that a concurrent RangeSearch cannot be trapped in a component or return incomplete results. This directly contradicts a stated contribution. Please either provide a proof that the intermediate states are connected, or empirically bound the disconnection duration and its effect on concurrent searches, or remove t
  2. [§5.1, Fig. 6 and Eq. (4)] The paper states the search time complexity 'can be expressed as O(n^{1/9} log(n^{1/9}))' and further extrapolates to a 1-billion-point dataset ('about 6.6 ms'). This appears to be a curve fit to measured points, not a complexity derived from the algorithm's structure. The fitted curves in Fig. 6 include arbitrary prefactors (e.g., 'n^(1/9)*log(n^(1.2/9))*600') with no residuals or confidence intervals. As presented, this is an empirical scaling observation, not an algorithmic complexity bound. Please either derive the exponent from the search/insertion process or explicitly label it as an empirical fit and provide the supporting data, error bars, and extrapolation caveats.
  3. [§4.1 and Table 2] The empirical claims are the central evidence for the paper's headline results, but the evaluation reports single runs without standard deviations or error bars, and the baseline hyperparameters are only 'documented on our project page' rather than in the paper or an appendix. Given that the claimed speedups are large (up to 250% on GloVe) and the experimental setup includes a reduced serial-scan curve with unspecified reduction, the reported numbers are not fully reproducible from the manuscript. Please provide multiple runs with variance estimates for the main QPS/recall comparisons, and include all hyperparameters (construction and search) for all methods in the paper.
minor comments (6)
  1. [§4.3, last paragraph] The text refers to 'Figure 2' when discussing exploration curves; this should be Figure 5.
  2. [Throughout] The abstract and §4.1 refer to 'SSG' while the rest of the paper uses NSSG; please make the naming consistent.
  3. [Table 2] The table formatting appears broken in places (especially the EG and crEG rows), making the reported memory/timing values difficult to parse. Please reformat and double-check the alignment.
  4. [§4.1] The sentence 'The Audio dataset is an outlier due to its smaller size, resulting in less pronounced differences' is speculative without supporting evidence; please either provide a quantitative justification or soften the claim.
  5. [§4.1] The serial scan curve uses a 'reduced base data set' but no reduction factor or procedure is given. Please specify the subset size and selection scheme.
  6. [§3.2] The paper lists four neighbor selection schemes (A–D) but does not provide a table of the dataset-dependent choices used in the experiments. Since scheme choice is a hyperparameter, it should be disclosed for each dataset.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: reported search-performance claims are measured against external baselines; the δN objective is not conflated with the reported outcome.

full rationale

I walked the claimed derivation chain. The construction (Algorithm 2) and edge optimization (Algorithms 4–5) use the internal metric δN to guide local edge changes, but the paper's headline claims are evaluated externally in terms of recall@k and queries per second against HNSW, NSG, NSSG, ONNG, etc. Thus δN is an optimization heuristic, not a renamed version of the measured outcome. No equation is defined in terms of the quantity it is supposed to predict, and no fitted parameter is later relabeled as a validated prediction. The MRNG approximation is adopted from external prior work [14] rather than from a self-citation chain, and the self-citations [3,4] only motivate exploratory-search applications; they are not load-bearing for the graph-construction or search-speed claims. The O(n^{1/9} log n) complexity statement is an empirical curve fit from Section 5.1, not a first-principles derivation, so it carries extrapolation risk rather than circularity. Likewise, the dataset-dependent choice between selection schemes (C) and (D) was informed by experiments on the same datasets, which is a selection-on-test-data concern, not a circular reduction. I do flag one internal inconsistency that is outside circularity: Algorithm 4, Step (3) states the vertices {vB, vC} 'may become unreachable for vA and vD', and Step (6) reverts all changes if no solution is found, which conflicts with the abstract's claim that both manipulation algorithms 'guarantee graph connectivity at any time'. This is a correctness/consistency gap in the concurrent-service story, but it does not make the measured search-speed results depend by construction on the inputs. Overall, the central derivation and evaluation are self-contained with respect to external benchmarks, so the circularity score is 0.

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

The paper introduces no new physical or conceptual entities; it introduces a small set of hyperparameters and relies on heuristic assumptions about MRNG approximation and delta_N minimization.

free parameters (5)
  • degree d (even regularity)
    The core design parameter: each vertex has exactly d neighbors. d>=4 is required; exact value used in experiments is not stated in the text (only on the project page). It controls memory, connectivity, and search speed.
  • construction search parameters k_ext, eps_ext (Algorithm 2)
    Control the candidate pool for attaching each new vertex. Values not given in the paper text; documented on the project page. The nearest-neighbor quality of the final graph depends on them.
  • optimization parameters k_opt, eps_opt, i_opt (Algorithm 4)
    Control edge-swap exploration depth and number of iterations. Affect the improvement in delta_N and the indexing time reported in Table 2.
  • neighbor selection scheme (A/B/C/D) = scheme C for high-LID sets, scheme D otherwise
    A discrete choice made after observing dataset LID in Section 4 experiments; influences construction behavior and is fitted to the evaluation datasets.
  • scaling-law coefficients = insert ~ log(n)/1.5 ms; search ~ n^(1/9)*log(n^(1.2/9))*600 us
    Empirically fitted to the SIFT1M scaling curves in Figure 6 and used to extrapolate insertion time at 1B points. These are fit parameters, not derived constants.
assumptions (3)
  • standard math Handshaking lemma and Eulerian graph theorem: a connected graph with all even degrees has no bridges, hence remains connected after removing one edge.
    Used in Section 3.1 to justify |E| = |V|d/2 and 2-edge connectivity, and to claim that edge removal during construction cannot disconnect the graph.
  • domain assumption Approximating a Monotonic Relative Neighborhood Graph (MRNG) yields monotonic search paths and O(log n)-like navigation.
    The paper relies on MRNG theory from [14] but only provides Algorithm 3, a common-neighbor approximation; there is no proof that the approximation preserves the monotonic-path guarantee.
  • ad hoc to paper Reducing average neighbor distance delta_N while keeping even regularity improves recall/speed trade-off.
    This is the central heuristic underwriting the edge-optimization algorithm (Section 3.3); it is supported only by the experiments in Section 5.2, not derived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval." pith.science (2026). https://pith.science/paper/CYQKIKTO

@misc{pith2026260727623,
  author       = {Pith},
  title        = {Pith review of: An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CYQKIKTO}},
  note         = {Machine review of arXiv:2607.27623}
}
read the original abstract

As datasets and the dimensionality of feature vectors continue to grow, Approximate Nearest Neighbor Search (ANNS) in large multimedia databases becomes increasingly relevant. Graph-based approaches have demonstrated to offer the best trade-off between retrieval precision and search time. Despite their ability to deliver search times several orders of magnitude faster than exact search techniques, existing methods suffer from slow constructions speeds or high memory requirements. This paper presents a "continuous refining Exploration Graph" (crEG), a novel approach for rapidly constructing a compact exploration graph with state-of-the-art search performance. Additionally, it provides the ability to enhance its effectiveness even further through an optional edge optimization algorithm. Both algorithms are specifically designed to produce and operate on undirected graphs with even degrees and guarantee graph connectivity at any time, a property particularly valuable for "exploratory search", where the query is part of the database elements. Although such queries provide an advantageous starting point for graph search algorithms, they have been rarely considered in the context of ANNS, yet are crucial for recommendation and exploration systems. Our experiments demonstrate high efficiency in ANNS does not necessarily translate to a good performance in "exploratory search".

Figures

Figures reproduced from arXiv: 2607.27623 by the authors.

Figure 1
Figure 1. A 2D toy example. Left: Smallest possible [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A 2D example for extending a crEG4, showing the final graphs for various selection schemes for choosing the neighbor 𝑛 in step (4): (A) the neighbor closest to 𝑣. (B) the neighbor with the shortest edge. (C) the neighbor with the longest edge. (D) the neighbor where the 𝛿N (𝑉 ) decreases the most. Selection Scheme [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The continuous edge optimization process is illustrated by [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The number of queries per second (QPS) in relation to recall@100 for approximate nearest neighbor search was tested [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Exploration performance measured by recall@1000 in relation to the number of queries per second (QPS). Various [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 7
Figure 7. Figure 7: Left: Edge optimization transforms a random even [PITH_FULL_IMAGE:figures/full_fig_p008_7.png]
Figure 6
Figure 6. Figure 6: Influence of index size on indexing speed (left) and [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 1 canonical work pages

  1. [1]

    2011.KGraph: A Library for Approximate Nearest Neighbor Search

    aaalgo. 2011.KGraph: A Library for Approximate Nearest Neighbor Search. https: //github.com/aaalgo/kgraph

    2011

  2. [2]

    Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst.87 (2020)

    2020

  3. [3]

    Kai Uwe Barthel, Nico Hezel, Konstantin Schall, and Klaus Jung. 2019. Real- Time Visual Navigation in Huge Image Sets Using Similarity Graphs.. InACM Multimedia, Laurent Amsaleg, Benoit Huet, Martha A. Larson, Guillaume Gravier, Hayley Hung, Chong-Wah Ngo, and Wei Tsang Ooi (Eds.). ACM, Nice, France, 2202–2204

    2019

  4. [4]

    Kai Uwe Barthel, Nico Hezel, Konstantin Schall, and Klaus Jung. 2023. Navigu.Net: NAvigation in Visual Image Graphs Gets User-Friendly. InProceedings of the 2023 ACM International Conference on Multimedia Retrieval(Thessaloniki, Greece) (ICMR ’23). Association for Computing Machinery, New York, NY, USA, 654–658. https://doi.org/10.1145/3591106.3592248

    arXiv 2023

  5. [5]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching.Commun. ACM18 (September 1975), 509–517. Issue 9. https://doi. org/10.1145/361002.361007

    arXiv 1975

  6. [6]

    Patrick Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2023. FINGER: Fast Inference for Graph-Based Approximate Nearest Neighbor Search. InProceedings of the ACM Web Conference 2023(Austin, TX, USA)(WWW ’23). Association for Computing Machinery, New York, NY, USA, 3225–3235. https://doi.org/10.1145/3543507.3583318

    arXiv 2023

  7. [7]

    2016.NNS Benchmark: Evaluating Approximate Nearest Neighbor Search Algorithms in High Dimensional Euclidean Space

    DBAIWangGroup. 2016.NNS Benchmark: Evaluating Approximate Nearest Neighbor Search Algorithms in High Dimensional Euclidean Space. https: //github.com/DBAIWangGroup/nns_benchmark

    2016

  8. [8]

    Delaunay

    B. Delaunay. 1933. Neue Darstellung der geometrischen Kristallographie. Zeitschrift für Kristallographie - Crystalline Materials84, 1-6 (1933), 109–149. https://doi.org/doi:10.1524/zkri.1933.84.1.109

    work page doi:10.1524/zkri.1933.84.1.109 1933

Show all 47 references
  1. [9]

    Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures. InProceedings of the 20th International Conference on World Wide Web(Hyderabad, India)(WWW ’11). ACM, New York, NY, USA, 577–586

    2011

  2. [10]

    Leonhard Euler. 1736. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae8 (1736), 128–140

  3. [11]

    Elena Facco, Maria d’Errico, Alex Rodriguez, and Alessandro Laio. 2018. Estimat- ing the intrinsic dimension of datasets by a minimal neighborhood information. CoRRabs/1803.06992 (2018)

    2018 arXiv

  4. [12]

    Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph.CoRRabs/1609.07228 (2016)

    2016 arXiv

  5. [13]

    Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility.IEEE Transactions on Pattern Analysis and Machine Intelligence44, 8 (2022), 4139–4150. https://doi.org/10.1109/...

    2022

  6. [14]

    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 (2019), 461–474

    2019

  7. [15]

    Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs.. InCVPR. IEEE Computer Society, 5713–5722

    2016

  8. [16]

    Ville Hyvönen, Elias Jääsaari, and Teemu Roos. 2022. A Multilabel Classification Framework for Approximate Nearest Neighbor Search. InAdvances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran As...

    2022

  9. [17]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: To- wards 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

  10. [18]

    Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data. CoRRabs/1810.07355 (2018)

    2018 arXiv

  11. [19]

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs.IEEE Transactions on Big Data7, 3 (2019), 535–547

    2019

  12. [20]

    Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search.IEEE Trans. Pattern Anal. Mach. Intell.33, 1 (2011), 117–128

    2011

  13. [21]

    Andersen, and Yuxiong He

    Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. 2020. Im- proving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. InProceedings of the 2020 ACM SIGMOD International Conference on Management of Data(Portland, OR, USA)(SIGMOD ’20). A...

    2020

  14. [22]

    Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement.IEEE Trans. Knowl. Data Eng. 32, 8 (2020), 1475–1488

    2020

  15. [23]

    Peng-Cheng Lin and Wan-Lei Zhao. 2019. Graph based Nearest Neighbor Search: Promises and Failures.CoRRabs/1904.02077 (2019). arXiv:1904.02077

    2019 arXiv

  16. [24]

    2018.Hnswlib: fast approximate nearest neighbor search

    Yury Malkov. 2018.Hnswlib: fast approximate nearest neighbor search. https: //github.com/nmslib/hnswlib

    2018

  17. [25]

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

  18. [26]

    Malkov and D

    Yury A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell.42, 4 (2020), 824–836

    2020

  19. [27]

    Gonzalo Navarro. 2002. Searching in metric spaces by spatial approximation. VLDB J.11, 1 (2002), 28–46

    2002

  20. [28]

    Rodrigo Paredes and Edgar Chávez. 2005. Using the k-Nearest Neighbor Graph for Proximity Searching in Metric Spaces.. InSPIRE (Lecture Notes in Computer Science, Vol. 3772), Mariano P. Consens and Gonzalo Navarro (Eds.). Springer, 127–138

    2005

  21. [29]

    Youngki Park, Sungchan Park, Woosung Jung, and Sang goo Lee. 2015. Reversed CF: A fast collaborative filtering algorithm using a k-nearest neighbor graph. Expert Syst. Appl.42, 8 (2015), 4022–4028

    2015

  22. [30]

    Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. InProceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532–1543

    2014

  23. [31]

    Alexander Ponomarenko, Nikita Avrelin, Bilegsaikhan Naidan, and Leonid Boytsov. 2014. Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search

    2014

  24. [32]

    Vieira, and Daniel S

    Larissa Capobianco Shimomura, Rafael Seidi Oyamada, Marcos R. Vieira, and Daniel S. Kaster. 2021. A survey on graph-based methods for similarity searches in metric spaces.Inf. Syst.95 (2021), 101507

    2021

  25. [33]

    Karen Simonyan and Andrew Zisserman. 2015. Very Deep Convolutional Net- works for Large-Scale Image Recognition.. InICLR, Yoshua Bengio and Yann LeCun (Eds.)

    2015

  26. [34]

    Kohei Sugawara, Hayato Kobayashi, and Masajiro Iwasaki. 2016. On Approxi- mately Searching for Similar Word Embeddings.. InACL (1). The Association for Computer Linguistics, Berlin, Germany

    2016

  27. [35]

    Toussaint

    Godfried T. Toussaint. 1980. The relative neighbourhood graph of a finite planar set.Pattern Recognition12, 4 (1980), 261–268. https://doi.org/10.1016/0031- 3203(80)90066-7

    1980 doi

  28. [36]

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xi- angyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021....

    2021

  29. [37]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Com- prehensive Survey and Experimental Comparison of Graph-Based Approxi- mate Nearest Neighbor Search.Proc. VLDB Endow.14, 11 (jul 2021), 1964–1978. https://doi.org/10.14778/3476249.3476255

    2021

  30. [38]

    Zhe Wang, Wei Dong, William Josephson, Qin Lv, Moses Charikar, and Kai Li

  31. [39]

    Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data.Proc. VLDB Endow.13, 12 (2020), 3152–3165

    2020

  32. [40]

    2016.Neighborhood Graph and Tree for Indexing High-dimensional Data

    yahoojapan. 2016.Neighborhood Graph and Tree for Indexing High-dimensional Data. https://github.com/yahoojapan/NGT

    2016

  33. [41]

    Artem Babenko Yandex and Victor Lempitsky. 2016. Efficient Indexing of Billion- Scale Datasets of Deep Descriptors. In2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055–2063. https://doi.org/10.1109/CVPR.2016. 226

    2016 doi

  34. [42]

    Kang Zhao, Pan Pan, Yun Zheng, Yanhao Zhang, Changxu Wang, Yingya Zhang, Yinghui Xu, and Rong Jin. 2019. Large-Scale Visual Search with Binary Dis- tributed Graph at Alibaba.. InCIKM, Wenwu Zhu, Dacheng Tao, Xueqi Cheng, Peng Cui, Elke A. Rundensteiner, David Carmel, Qi He, an...

    2019

  35. [43]

    2017.efanna: An extremely fast approximate nearest neighbor graph construction algorithm framework

    ZJULearning. 2017.efanna: An extremely fast approximate nearest neighbor graph construction algorithm framework. https://github.com/ZJULearning/efanna_ graph

    2017

  36. [44]

    2018.NSG: Navigating Spread-out Graph For Approximate Nearest Neighbor Search

    ZJULearning. 2018.NSG: Navigating Spread-out Graph For Approximate Nearest Neighbor Search. https://github.com/ZJULearning/nsg

    2018

  37. [45]

    2019.SSG: Code for Satellite System graphs

    ZJULearning. 2019.SSG: Code for Satellite System graphs. https://github.com/ ZJULearning/SSG

    2019

  38. [2007]

    InSIGMETRICS, Leana Golubchik, Mostafa H

    Sizing sketches: a rank-based analysis for similarity search.. InSIGMETRICS, Leana Golubchik, Mostafa H. Ammar, and Mor Harchol-Balter (Eds.). ACM, 157– 168

  39. [2014]

    Syst.45 (2014), 61–68

    Approximate nearest neighbor algorithm based on navigable small world graphs.Inf. Syst.45 (2014), 61–68

    2014

Pith tools

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