Pith. sign in

REVIEW 3 major objections 6 minor 68 references

Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities

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

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

Pith's one-line read GATE speeds up graph-based nearest-neighbor search by learning the best entry node for each query, cutting search paths by 30-40%.

desk verdict A solid plug-and-play entry-point selection layer for graph ANNS, but the main speedup claim rests on a train/test split that the paper never states. read the letter →

arxiv 2506.15986 v1 pith:7L6A463F submitted 2025-06-19 cs.DB cs.IR

Jiancheng Ruan , Tingyang Chen , Renchi Yang , Xiangyu Ke , Yunjun Gao This is my paper
classification cs.DBcs.IR
keywords approximatenearestneighborsearchgraph-basedindexentrypointselectionhubnodestwo-towermodelcontrastivelearninghigh-dimensionalvectorsqueryawareness
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 argues that the main remaining inefficiency in graph-based approximate nearest neighbor search (ANNS) is not the graph itself but where the traversal starts: a poor entry point makes the search take a long path through the graph and can trap it in a local region. GATE is proposed as a lightweight module that sits on top of any existing proximity graph and learns to recommend an optimal entry node (a 'hub node') for each incoming query. The hub nodes are cluster centroids of the dataset, each enriched with a learned representation that combines the local topology of the underlying graph with patterns distilled from historical queries. On five benchmarks, the paper reports that this entry-point recommendation reduces search path length by 30–40% and improves query throughput by 1.2–2.0× over state-of-the-art graph indexes. If true, the approach would make existing graph indexes substantially faster without altering their structure, and it would make them more robust to query distributions that differ from the base data.

What carries the argument

The load-bearing object is the set of hub nodes $\mathbb{V}$ together with the two-tower contrastive model that produces their latent representations. Hub nodes are extracted by hierarchical balanced $k$-means (HBKM), which partitions the dataset into balanced clusters and takes the nearest neighbor of each cluster centroid as a hub; the balance penalty $\lambda(|C_{ij}|-|C_i|/k)^2$ keeps clusters comparable in size so hubs spread across the space. Each hub is then augmented with a topological feature obtained by sampling an $h$-hop subgraph around it (mixing near and far neighbors) and encoding that subgraph with a graph embedding method such as Graph2Vec, and the hub's data vector and topological vector are fused by a multi-head attention fusion embedding. A contrastive loss of the InfoNCE form aligns each hub's fused representation with positive historical queries (those whose top-1 neighbor is within a small hop tolerance of the hub) and pushes it away from negative queries. The final refined hub representations are linked by cosine similarity into the high-tier navigation graph, so that a greedy search over hub nodes (not over the whole data graph) selects the entry point for the query, cutting the number of hops spent inside the base graph.

What would settle it

Split each dataset's query set into disjoint training and test halves, train GATE on the training half, and measure QPS at 95% recall on the test half against NSG; if the speedup drops below the reported 1.2×, the adaptive awareness is partly memorization rather than generalization.

Watch

Extended reading notes

Core claim

GATE's central claim is that the optimal entry point for a query in a proximity graph can be learned, rather than chosen heuristically, and that doing so shortens the search path length $\ell$ enough to yield a 1.2–2.0× query-speedup with no modification of the underlying index. To establish this, the paper (i) extracts a small set of hub nodes $\mathbb{V}$ via hierarchical balanced $k$-means, so each cluster of the high-dimensional space is represented by one navigation point; (ii) samples a local subgraph around each hub node and encodes it with a graph embedding method, giving each hub a topological signature; and (iii) trains a contrastive two-tower model in which the hub nodes and historical queries are projected into a shared space, with positive and negative query samples defined by how close the query's true top-1 neighbor is (in hop count) to the hub. The refined hub representations are connected by cosine similarity into a 'high-tier' navigation graph, on which greedy search finds a good entry hub for a new query at low inference cost. The paper frames this as 'recommending' an entry point, borrowing the two-tower paradigm from recommendation systems.

Load-bearing premise

GATE's gains rest on the assumption that the historical queries used to define positive and negative training samples are a good proxy for the queries that will actually arrive at search time—and that reported speedups are measured on queries the model has not already memorized.

Editorial extensions

If this is right

  • Any existing graph-based ANNS index can be accelerated by attaching GATE as a plug-in, because GATE only changes the traversal's entry point and leaves the underlying graph structure untouched.
  • The search-path component $\ell$ of the $O(d r \ell)$ query complexity, which prior work largely left unoptimized, becomes the main lever of improvement, with reported reductions of 30–40% against NSG at 95% recall.
  • Graph indexes become more robust to distribution mismatch between base data and queries: on Laion3M and Text2Image10M, GATE is the top performer on both in-distribution (image) and out-of-distribution (text) queries, with only a 1.2% gap between query types.
  • Entry-point optimization complements rather than replaces existing strategies such as multi-layer structures (HNSW, HVS) and LSH-based entry selection (LSH-APG), and in the reported experiments it outperforms both classes.
  • The method exploits historical query logs, so its gains are largest for recall@1, where the choice of entry point matters most, and it can be retrained as new logs arrive.

Reading between the lines

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

  • A direct test of the paper's generalization claim would split each dataset's historical queries into disjoint training and evaluation sets; if the speedup persists on held-out queries, the mechanism is learning a transferable entry-point rule, and if it collapses, the reported gains partly measure fit to the test distribution.
  • The hub-node design is likely to pay off most on datasets with pronounced cluster structure, since hubs are cluster centroids; on uniform or single-blob data the representation may be redundant and the speedup could shrink — a boundary the paper does not explore.
  • Because the high-tier navigation graph links hubs by cosine similarity, hubs that serve similar queries become neighbors; this suggests an online fine-tuning extension in which GATE retrains only the two-tower model on recent queries to track drifting query distributions without rebuilding the base graph.
  • The 'recommendation' framing invites swapping the two-tower model for other learned-retrieval devices such as approximate maximum-inner-product search, trading training cost against inference latency, though the paper does not test such alternatives.
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 GATE, a plug-in module for graph-based approximate nearest neighbor search. It extracts a set of hub nodes via hierarchical balanced k-means, distills topological features from sampled subgraphs around hubs, and learns query-aware hub representations with a contrastive two-tower model trained on historical queries. A small navigation graph over hubs is then used to choose the entry point for greedy search on the underlying index. The evaluation compares GATE with HNSW, HVS, LSH-APG, NSG, and NSSG on five datasets and reports 1.2-2.0x QPS speedups, 30-40% path-length reductions, ablations, and parameter sensitivity.

Significance. If the claimed results hold, GATE is a useful practical contribution: it is a lightweight, index-agnostic accelerator with released code, and the idea of learning hub entry points from historical queries is interesting. The main significance is bounded by the evaluation protocol: the paper never states that the queries used to construct the contrastive training labels are disjoint from the queries used to measure QPS and path length. Because positive/negative labels are defined by running the same search procedure that is measured during evaluation, overlap would make the speedup a measure of memorization rather than generalization. The correctness of the "cosine similarity is a metric" justification also needs attention. These are fixable with an explicit train/test split and corrected theoretical statement, but they are central to the paper's claim.

major comments (3)
  1. [§4.2 and §5.1] The paper never states that the query set Q used for positive/negative sample generation in Definition 4 and Section 4.2 is disjoint from the query set used for evaluation in Section 5.1 (Table 2 lists 1,000/100,000 queries per dataset). Since positive/negative labels are created by running Algorithm 1 from each hub to the top-1 result of each query, using the same queries for evaluation would directly test the model's fit to the training labels rather than its ability to generalize to unseen queries. Please report the exact split procedure, the number of training queries, and ideally repeat the main experiment (Figure 5 and Table 3) with held-out queries.
  2. [§5.2, Table 4] The numeric claims in the ablation text do not match Table 4. From Table 4, GATE vs GATE w/o H gives reductions of 5.3%, 8.9%, and 11.5% on Gist1M, Sift10M, and Text2Image10M (average 8.6%), while the text reports "an average improvement of 6.9%"; GATE vs GATE w/o FE averages about 6.7%, not "8%"; and "without this loss, performance drops by approximately 30%" is inconsistent with the GATE w/o L row, where the hop count increases by 51% on Gist1M (from 7566 to 11424) and on Text2Image10M is only 3.9% better than NSG. The text and table need to be reconciled so the ablation conclusions are verifiable.
  3. [§4.3] The statement "Cosine similarity satisfies the properties of a metric [53]" is incorrect: for vectors separated by angles 0°, 60°, and 120°, cosine distance (1 − cos) gives 1.5 > 0.5 + 0.5, violating the triangle inequality. The claimed guarantee that Algorithm 1 converges on the hub navigation graph therefore lacks the stated basis. Please either use angular distance (a true metric) for the hub graph construction, cite a correct convergence argument, or explicitly weaken the claim to an empirical one.
minor comments (6)
  1. [§4.3] The sentence "minimizing the cosine similarity between hub node and positive query representations while maximizing the distance to negative samples" is opposite to Eq. (4); it should say "maximizing similarity to positives and minimizing similarity to negatives".
  2. [§5.1] Although Section 5.1 states each query experiment is repeated ten times, no variance or error bars are reported in Figure 5 or Table 3; report mean ± standard deviation or otherwise justify aggregation.
  3. [Table 2 and §5.2] Table 2 lists Text2Image10M query size as 100,000, but Section 5.2 says 1000 queries are used for the path-length and out-of-distribution experiments; clarify the relationship between the 100,000-query set and the 1000-query samples.
  4. [§5.1] Reference [42] is cited for HNSW in the competitor list, but [42] is "Hierarchical clustering-based graphs..."; the HNSW reference should be [41] (Malkov and Yashunin).
  5. [§4.1] Typo: "We apply HKBM" should read "HBKM", matching Algorithm 2 and Definition 3.
  6. [§4.3] In the hub graph construction, the edge-building parameter s (number of most similar hub neighbors) is mentioned as s ≪ |V| but is not listed in the parameter settings in Section 5.1; specify its value or state the tuning procedure.

Circularity Check

1 steps flagged · score 6.0 of 10

The headline speedup is not guarded against in-sample overfitting: the paper never states that the query set used to train the two-tower model (Section 4.2) is disjoint from the 1,000-query evaluation set (Section 5.2), so the reported 1.2-2.0x speedup and 30-40% path-length reduction may measure fit to the evaluation queries rather than generalization to unseen queries.

  1. fitted input called prediction [Section 4.2 (Definition 4, Query-aware Sample Generation) and Section 5.2 (Exp-1, Table 3)]
    "In practice, we generate these samples by applying Algorithm 1 on NSG for each query q∈Q, and then assign them to the positive and negative sample queues of the corresponding hub node... we evaluated search path lengths on three datasets using 1000 queries. Table 3 shows that GATE reduces the search path length by 30–40% compared to the baseline."

    Definition 4 labels each hub V_i for each query q by H(q,V_i), the hop count from V_i to q's top-1 result on NSG; the contrastive loss (Eq. 4) then trains the hub embeddings so that queries with small H(q,V_i) are similar to V_i. Table 3's reported metric, search path length ℓ, is the same hop-count quantity measured from the GATE-selected entry hub on the same underlying NSG. The experimental section never states that the 1,000-query evaluation set is held out from the 'historical queries' Q used in Section 4.2; Table 2 lists the dataset query sets as the only source of queries.

full rationale

No self-citation chain or imported uniqueness theorem is load-bearing; the authors' own prior works [12,13] are not used to justify the core mechanism, and the contrastive-loss citation [14] is external. The central empirical comparison against HNSW, NSG, NSSG, HVS, and LSH-APG is self-contained on standard benchmarks. The only material circularity risk is the training/evaluation query overlap described above. Because the paper does not document a train/test split of the query set, the headline speedup cannot be certified as an out-of-sample prediction. This is a protocol gap rather than a demonstrated identity, so the score is set to 6 (partial circularity) rather than 8-10.

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

The method rests on hand-chosen structural hyperparameters (hub count, hop limit, sample thresholds, penalty) and on domain assumptions about clusterability, query stationarity, and the informativeness of subgraph embeddings. The trained two-tower weights are fitted to historical queries, making the query train/test split the decisive validity condition.

free parameters (8)
  • number of hub nodes |V| = 512
    Hand-chosen for all datasets; controls the size of the navigation graph and model capacity. Not swept in the sensitivity analysis.
  • subgraph sampling max hop h = 5
    Hand-chosen; Figure 7 shows QPS varies with h in {3,5,7,9}, with h=5 a good default.
  • positive sample tolerance t_pos = 3
    Hand-chosen; Figure 7 shows t_pos=3 optimal in {1,3,5,7} on Sift10M.
  • negative sample tolerance t_neg = 15
    Hand-chosen; sensitivity omitted but stated to follow a similar trend.
  • cluster balance penalty lambda = not specified in paper
    Introduced in Algorithm 2 (HBKM) to control cluster size balance; no default value is given in Section 5.1.
  • contrastive temperature tau = not specified in paper
    Appears in Equations 2 and 4; no value reported.
  • training hyperparameters (learning rate, batch size, epochs) = lr=5e-5, batch=8192, epochs=200
    Reported in Section 5.1; standard choices, but influence the learned hub representations.
  • two-tower model weights = trained on historical queries
    The projection network parameters are learned to minimize the contrastive loss; their generalization depends on the query train/test split.
assumptions (5)
  • domain assumption High-dimensional vector data exhibits clusterability that can be captured by balanced hierarchical k-means (HBKM).
    Section 4.1 bases the selection of hub nodes on clustering behavior, citing [46]. If the data does not cluster, hub selection reduces to quasi-random sampling and the navigation graph loses its intended structure.
  • domain assumption The historical query set Q is representative of future query distributions, and query distributions are relatively consistent over time.
    Section 4.2 states 'Query distributions typically exhibit relative consistency, allowing us to leverage multiple historical queries as Q'. This justifies using historical queries to define positive/negative samples for all future queries.
  • domain assumption Graph2Vec embeddings of sampled subgraphs encode topological semantics that are informative for entry-point selection.
    Section 4.2 uses Graph2Vec to project irregular subgraphs into fixed-dimensional features. The paper provides no independent validation of these embeddings beyond the end-to-end downstream result.
  • ad hoc to paper Cosine similarity satisfies the metric properties needed for greedy search on the hub navigation graph to converge.
    Section 4.3 asserts 'Cosine similarity satisfies the properties of a metric [53]'. Standard cosine similarity does not satisfy the triangle inequality in general; the paper does not specify the normalization or restricted domain that would make this true.
  • domain assumption The contrastive two-tower objective optimized on historical queries transfers to unseen queries.
    This is the generalization premise underlying the query-awareness claim; it is unverified because no train/test split of queries is described in Section 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities." pith.science (2026). https://pith.science/paper/7L6A463F

@misc{pith2026250615986,
  author       = {Pith},
  title        = {Pith review of: Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7L6A463F}},
  note         = {Machine review of arXiv:2506.15986}
}
read the original abstract

Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces finds extensive applications in databases, information retrieval, recommender systems, etc. While graph-based methods have emerged as the leading solution for ANNS due to their superior query performance, they still face several challenges, such as struggling with local optima and redundant computations. These issues arise because existing methods (i) fail to fully exploit the topological information underlying the proximity graph G, and (ii) suffer from severe distribution mismatches between the base data and queries in practice. To this end, this paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness, as a lightweight and adaptive module atop the graph-based indexes to accelerate ANNS. Specifically, GATE formulates the critical problem to identify an optimal entry point in the proximity graph for a given query, facilitating faster online search. By leveraging the inherent clusterability of high-dimensional data, GATE first extracts a small set of hub nodes V as candidate entry points. Then, resorting to a contrastive learning-based two-tower model, GATE encodes both the structural semantics underlying G and the query-relevant features into the latent representations of these hub nodes V. A navigation graph index on V is further constructed to minimize the model inference overhead. Extensive experiments demonstrate that GATE achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.

Figures

Figures reproduced from arXiv: 2506.15986 by the authors.

Figure 1
Figure 1. Visualizing NSG on a sample of Sift10M points with t-SNE and K-means into 4 clusters [54] [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Search path length (ℓ) across different query types on Laion3M and Text2image10M. queries against image databases is a common requirement. How￾ever, even within a shared latent space, indexes optimized for dif￾ferent modalities exhibit significant performance disparities [10]. While effectively supporting image-to-image retrieval, performance can degrade substantially for text-to-image retrieval. To quantify this mo… view at source ↗
Figure 3
Figure 3. A pipeline of GATE (§4.1); (2) extracting topological features and query distribution information based on these hub nodes (§4.2); and (3) constructing the adaptive high-tier navigation graph using a two-tower model (§4.3). While we use NSG as an example underlying graph in this paper, GATE can be applied to other graph indexes as well. The overall architecture of GATE is illustrated in [PITH_FULL_IMAGE:figures/ful… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: An example of subgraph sampling for V1 (ℎ = 2). the hop count of the shortest path from V𝑖 to the nearest neighbor of query 𝑞 ∈ Q in 𝐺. A positive sample 𝑞𝑝𝑜𝑠 for V𝑖 is a query 𝑞𝑝𝑜𝑠 ∈ Q such that 𝐻(𝑞𝑝𝑜𝑠 , V𝑖) ≤ min𝑞∈ Q 𝐻(𝑞, V𝑖) + 𝑡𝑝𝑜𝑠 , where 𝑡𝑝𝑜𝑠 is a pre-defined tole…
Figure 5
Figure 5. Figure 5: ANNS Performance on five Datasets. The top right is better. for indexing and a single thread for query execution. Each query experiment is repeated ten times, and the average result is reported to reduce system variability. For all algorithms, we employed the grid sear…
Figure 6
Figure 6. Figure 6: Evaluation on different query types. the two-tower model. Cosine similarity contributes to stable and effective GATE training. Our ablation study shows that without this loss, performance drops by approximately 30%. Exp-3: Parameter Sensitivity (RQ3). We assess the eff…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

68 extracted references · 39 canonical work pages

  1. [53]

    Kihyuk Sohn. 2016. Improved deep metric learning with multi-class n-pair loss objective.Advances in neural information processing systems29 (2016)

    work page 2016

  2. [1]

    Hervé Abdi and Lynne J Williams. 2010. Principal component analysis.Wiley interdisciplinary reviews: computational statistics2, 4 (2010), 433–459

    2010

  3. [2]

    Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report.arXiv preprint arXiv:2303.08774 (2023)

    arXiv 2023

  4. [3]

    Laurent Amsaleg and Hervé Jegou. 2010. Datasets for approximate nearest neighbor search. (2010)

    work page 2010

  5. [4]

    Anon. unknown. Tiny5M. Retrieved January 1, 2025 from https://www.cse.cuhk. edu.hk/systems/hash/gqr/datasets.html

    work page 2025

  6. [5]

    Franz Aurenhammer. 1991. Voronoi diagrams—a survey of a fundamental geo- metric data structure.ACM Computing Surveys (CSUR)23, 3 (1991), 345–405

    work page 1991

  7. [6]

    Artem Babenko Dmitry Baranchuk and Artem Babenko. 2021. Text-to-Image dataset for billion-scale similarity search.Retrieved August23 (2021), 2023

    work page 2021

  8. [7]

    Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. 2019. Learning to route in similarity graphs. InInternational Conference on Machine Learning. PMLR, 475–484

    work page 2019

Show all 68 references
  1. [8]

    Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger

  2. [9]

    Brankica Bratić, Michael E Houle, Vladimir Kurbalija, Vincent Oria, and Miloš Radovanović. 2018. NN-Descent on high-dimensional data. InProceedings of the 8th International Conference on Web Intelligence, Mining and Semantics. 1–8

    2018

  3. [10]

    Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X Sean Wang. 2024. Roar- Graph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Near- est Neighbor Search.VLDB17, 11 (2024), 2735–2749

    2024

  4. [11]

    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. 3225– 3235

    2023

  5. [12]

    Tingyang Chen, Cong Fu, Xiangyu Ke, Yunjun Gao, Yabo Ni, and Anxiang Zeng

  6. [13]

    Tingyang Chen, Cong Fu, Kun Wang, Xiangyu Ke, Yunjun Gao, Wenchao Zhou, Yabo Ni, and Anxiang Zeng. 2025. Maximum Inner Product is Query-Scaled Nearest Neighbor.arXiv preprint arXiv:2503.06882(2025)

    2025 arXiv

  7. [14]

    Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020. A simple framework for contrastive learning of visual representations. InICML. 1597–1607

    2020

  8. [15]

    Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep neural networks for youtube recommendations. InProceedings of the 10th ACM conference on recommender systems. 191–198

    2016

  9. [16]

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

    2004

  10. [17]

    DW Dearholt, N Gonzales, and G Kurup. 1988. Monotonic search networks for computer vision databases. InTwenty-Second Asilomar Conference on Signals, Systems and Computers, Vol. 2. IEEE, 548–553

    1988

  11. [18]

    Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. InProceedings of the 20th interna- tional conference on World wide web. 577–586

    2011

  12. [19]

    STEVEN FORTUNE. 1992. VORONOI DIAGRAMS and DELAUNAY TRIANGU- LATIONS.Computing In Euclidean Geometry(1992), 193–233

    1992

  13. [20]

    Cong Fu and Deng Cai. 2016. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph.arXiv preprint arXiv:1609.07228 (2016)

    2016 arXiv

  14. [21]

    Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility.IEEE Transactions on Pattern Analysis and Machine Intelligence44, 8 (2021), 4139–4150

    2021

  15. [22]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph.Proceedings of the VLDB Endowment12, 5 (2019), 461–474

    2019

  16. [23]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization for approximate nearest neighbor search. InProceedings of the IEEE conference on computer vision and pattern recognition. 2946–2953

    2013

  17. [24]

    Daniel Gillick, Alessandro Presta, and Gaurav Singh Tomar. 2018. End-to-end retrieval in continuous space.arXiv preprint arXiv:1811.08008(2018)

    2018 arXiv

  18. [25]

    Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. InVldb, Vol. 99. 518–529

    1999

  19. [26]

    Mihajlo Grbovic and Haibin Cheng. 2018. Real-time personalization using em- beddings for search ranking at airbnb. InProceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 311–320

    2018

  20. [27]

    Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, et al. 2022. Manu: a cloud native vector database management system.PVLDB15, 12 (2022), 3548–3561

    2022

  21. [28]

    Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 5713–5722

    2016

  22. [29]

    Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative filtering for implicit feedback datasets. In2008 Eighth IEEE international conference on data mining. Ieee, 263–272

    2008

  23. [30]

    Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search. Proceedings of the VLDB Endowment9, 1 (2015), 1–12

    2015

  24. [31]

    Tongwen Huang, Zhiqi Zhang, and Junlin Zhang. 2019. FiBiNET: combining fea- ture importance and bilinear feature interaction for click-through rate prediction. InProceedings of the 13th ACM conference on recommender systems. 169–177

    2019

  25. [32]

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

    1998

  26. [33]

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node.Advances in Neural Information Pro- cessing Systems32 (2019)

    2019

  27. [34]

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

    2010

  28. [35]

    Diederik P Kingma. 2014. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980(2014)

    2014 arXiv

  29. [36]

    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. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing S...

    2020

  30. [37]

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

    2019

  31. [38]

    Yingfan Liu, Jiangtao Cui, Zi Huang, Hui Li, and Heng Tao Shen. 2014. SK-LSH: an efficient index structure for approximate nearest neighbor search.Proceedings of the VLDB Endowment7, 9 (2014), 745–756

    2014

  32. [39]

    Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search.Proceedings of the VLDB Endowment15, 2 (2021), 246– 258

    2021

  33. [40]

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

  34. [41]

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

    2018

  35. [42]

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

  36. [43]

    Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. 2017. graph2vec: Learning distributed representations of graphs.arXiv preprint arXiv:1707.05005(2017)

    2017 arXiv

  37. [44]

    Mohammad Norouzi and David J Fleet. 2013. Cartesian k-means. InProceedings of the IEEE Conference on computer Vision and Pattern Recognition. 3017–3024

    2013

  38. [45]

    James Jie Pan, Jianguo Wang, and Guoliang Li. 2023. Survey of vector database management systems.arXiv preprint arXiv:2310.14021(2023)

    2023 arXiv

  39. [46]

    Lance Parsons, Ehtesham Haque, and Huan Liu. 2004. Subspace clustering for high dimensional data: a review.Acm sigkdd explorations newsletter6, 1 (2004), 90–105

    2004

  40. [47]

    François Petitjean, Germain Forestier, Geoffrey I Webb, Ann E Nicholson, Yanping Chen, and Eamonn Keogh. 2014. Dynamic time warping averaging of time series allows faster and more accurate classification. In2014 IEEE international conference on data mining. IEEE, 470–479

    2014

  41. [48]

    2012.Computational geometry: an introduction

    Franco P Preparata and Michael I Shamos. 2012.Computational geometry: an introduction. Springer Science & Business Media

    2012

  42. [49]

    Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021. Learning transferable visual models from natural language supervision. InInternational conference on machine learnin...

    2021

  43. [50]

    Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021. Learning Transferable Visual Models From Natural Language Supervision. InICML. 8748–8763

    2021

  44. [51]

    Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. 2015. Imagenet large scale visual recognition challenge.IJCV115 (2015), 211–252

    2015

  45. [52]

    Chanop Silpa-Anan and Richard Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1–8. Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities KDD...

    2008

  46. [54]

    Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. 2016. Visualizing large- scale and high-dimensional data. InProceedings of the 25th international conference on world wide web. 287–297

    2016

  47. [55]

    Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set.Pattern recognition12, 4 (1980), 261–268

    1980

  48. [56]

    Hongya Wang, Zhizheng Wang, Wei Wang, Yingyuan Xiao, Zeng Zhao, and Kaixiang Yang. 2020. A note on graph-based nearest neighbor search.arXiv preprint arXiv:2012.11083(2020)

    2020 arXiv

  49. [57]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A com- prehensive survey and experimental comparison of graph-based approximate nearest neighbor search.Proceedings of the VLDB Endowment14, 11 (2021), 1964–1978

    2021

  50. [58]

    Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. 2019. Sampling-bias-corrected neural modeling for large corpus item recommendations. InRecSys. 269–277

    2019

  51. [59]

    Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. 2022. Al- gorithm and system co-design for efficient subgraph-based graph representation learning.Proceedings of the VLDB Endowment15, 11 (2022), 2788–2796

    2022

  52. [60]

    Qiang Yue, Xiaoliang Xu, Yuxiang Wang, Yikun Tao, and Xuliyuan Luo. 2023. Routing-Guided Learned Product Quantization for Graph-Based Approximate Nearest Neighbor Search.arXiv preprint arXiv:2311.18724(2023)

    2023 arXiv

  53. [61]

    Minjia Zhang and Yuxiong He. 2019. Grip: Multi-store capacity-optimized high- performance nearest neighbor search for vector search engine. InProceedings of the 28th ACM International Conference on Information and Knowledge Management. 1673–1682

    2019

  54. [62]

    Minjia Zhang, Wenhan Wang, and Yuxiong He. 2022. GraSP: Optimizing Graph- based Nearest Neighbor Search with Subgraph Sampling and Pruning. InPro- ceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 1395–1405

    2022

  55. [63]

    Wan-Lei Zhao. 2018. k-NN graph construction: a generic online approach.arXiv preprint arXiv:1804.03032(2018)

    2018 arXiv

  56. [64]

    Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High- Dimensional Spaces.Proceedings of the VLDB Endowment16, 8 (2023), 1979–1991

    2023

  57. [1990]

    InProceedings of the 1990 ACM SIGMOD international conference on Management of data

    The R*-tree: An efficient and robust access method for points and rectangles. InProceedings of the 1990 ACM SIGMOD international conference on Management of data. 322–331

    1990

  58. [2014]

    Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems45 (2014), 61–68

    2014

  59. [2019]

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

    2019

  60. [2025]

    Stitching Inner Product and Euclidean Metrics for Topology-aware Maxi- mum Inner Product Search.arXiv preprint arXiv:2504.14861(2025)

    2025 arXiv

Pith tools

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