Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search

Kai Zheng; Liwei Deng; Penghao Chen; Tianfu Wang; Ximu Zeng; Yan Zhao

REVIEW 3 major objections 4 minor 60 references

Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search

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

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

Pith's one-line read DADE replaces exact distance comparisons in approximate nearest-neighbor search with a PCA-based estimate whose dimension count is chosen per candidate by hypothesis testing, and reports more than 40% higher queries per second on HNSW at…

desk verdict A practical data-aware DCO accelerator with believable empirical gains, but the theory is overclaimed and the failure-probability calibration may not transfer to actual search candidates. read the letter →

arxiv 2411.17229 v2 pith:2V6EMOIA submitted 2024-11-26 cs.DB cs.IR

Liwei Deng , Penghao Chen , Ximu Zeng , Tianfu Wang , Yan Zhao , Kai Zheng This is my paper · ORCID

classification cs.DBcs.IR

keywords approximatenearestneighborsearchdistancecomparisonoperationdata-awareestimationPCAprojectionadaptivedimensionselectionhypothesistestingHNSWIVF

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

Most approximate nearest-neighbor search algorithms spend most of their query time on distance comparison operations (DCOs): deciding whether a candidate object is close enough to the query to enter the current neighbor set. This paper proposes DADE, a drop-in replacement for those comparisons that estimates the Euclidean distance from a low-dimensional projection rather than computing it in the full space. The estimator is unbiased with respect to the data distribution, and the projection is chosen by PCA so that the estimation error has small variance in the sense of an upper-bound argument. A hypothesis test decides per candidate how many dimensions are needed before the comparison can be made safely. Integrated into IVF and HNSW, DADE is reported to improve queries per second by more than 40% on HNSW compared with ADSampling while keeping the same recall, which matters because DCOs are the dominant cost in many ANN systems.

What carries the argument

The load-bearing object is the data-aware orthogonal projection: an orthonormal matrix $W_D$ whose first $d$ columns are the top-$d$ eigenvectors of the data covariance matrix, i.e., a PCA projection. The identity that carries the argument rescales the low-dimensional squared distance by the eigenvalue ratio $\sum_{k=1}^{D}\lambda_k / \sum_{k=1}^{d}\lambda_k$, making the estimate unbiased, and the hypothesis-testing loop in the algorithm expands $d$ in steps of $\Delta d$, rejecting the null hypothesis $H_0: dis \le r$ as soon as the estimated distance exceeds $(1+\epsilon_d)r$. The PCA choice is what makes the estimator data-aware, and it is the premise on which the variance-optimality claim rests.

What would settle it

A concrete check is to run DADE inside HNSW or IVF with ground-truth neighbor labels and record, for objects that truly satisfy $dis \le r$, how often the hypothesis test rejects before reaching the full dimension; if this empirical failure rate systematically exceeds $\lfloor(D-1)/\Delta d\rfloor P_s$ on datasets whose near-query pairs differ from uniformly sampled pairs, the calibrated quantile assumption breaks.

Watch

Extended reading notes

Core claim

The central claim is that the dominant cost of approximate nearest-neighbor search, the repeated distance comparison between a query and a candidate object, can be made data-aware. For i.i.d. zero-mean random vectors $X_1, X_2$, an orthonormal matrix $W_D$, and its first $d$ columns $W_d$, the paper proves the unbiasedness identity $\mathbb{E}[\lVert X_1-X_2\rVert_2^2] = \frac{\sigma^2(1,D)}{\sigma^2(1,d)} \mathbb{E}[\lVert W_d^T(X_1-X_2)\rVert_2^2]$, where $\sigma^2(i,j) = \sum_{k=i}^{j} \mathrm{Var}(w_k^T X)$. Choosing $W_d$ as the top-$d$ principal components of the data covariance maximizes $\sigma^2(1,d)$ and, by an upper-bound argument, is claimed to minimize the variance of the estimation error. The resulting estimator is $\frac{\sum_{k=1}^{D}\lambda_k}{\sum_{k=1}^{d}\lambda_k}\lVert W_d^T(X_1-X_2)\rVert_2^2$, and a hypothesis test expands $d$ incrementally until the comparison $dis \le r$ can be decided at significance level $P_s$. The paper reports that as a plug-in into HNSW this raises queries per second by more than 40% over ADSampling on the DEEP dataset at the same recall.

Load-bearing premise

The reliability argument assumes that the error quantile measured on uniformly sampled data objects still applies to the candidates that actually reach the comparison step during search, even though those candidates are not uniformly sampled because they are conditioned on being near the query.

Editorial extensions

If this is right

Any ANN algorithm whose query bottleneck is distance comparisons can adopt DADE as a black-box replacement for its DCO step, without changing how candidates are generated.
Because most candidates are far from the query, the adaptive hypothesis test can reject them after a small number of dimensions, so the average cost per comparison drops well below one full-dimensional distance computation.
The Lemma 5 bound means that when a true distance exceeds the threshold the comparison is always decided correctly, while for true distances within the threshold the chance of a wrong rejection is bounded by $\lfloor(D-1)/\Delta d\rfloor P_s$.
At matched recall on the DEEP dataset, the reported QPS gain of more than 40% over ADSampling attributes the speedup to the DCO estimator itself rather than to any index-specific tuning.

Reading between the lines

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

A natural extension the paper does not explore is to condition the dimension schedule on the query's coarse location, for instance the cluster or graph region it lands in, since that changes the distribution of the candidates being compared.
The variance-optimality argument relies on an upper bound rather than an exact minimization, so a direct formula for the estimator variance would sharpen or qualify the claimed optimality and could turn the significance level $P_s$ from a tuned hyperparameter into a derived quantity.
Because the projection is computed once from the static dataset, DADE's advantage is most likely to persist on stationary in-memory indexes; on streaming data where the covariance drifts, the same projection would need periodic recomputation, a regime the paper does not cover.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Here's the short version. DADE is a sensible, incremental extension of ADSampling: it replaces the random orthogonal transform with PCA so that low-dimensional projections carry more variance, and it uses a data-calibrated hypothesis test to decide when to expand the dimension. The empirical work is substantial—six datasets, HNSW and IVF variants, recall/QPS tradeoff curves—and the reported 20-45% QPS gains at matched recall are believable as a within-subfield improvement. The abstract links a code repository, which helps reproducibility.

Where the paper gets soft is the theory. The 'unbiased estimation' in Lemma 3 is an identity for expected squared distances of iid random pairs. The decision procedure uses the square root of that estimate on a fixed pair, and squared-distance unbiasedness does not make the distance estimate unbiased. The abstract says the distance estimation is unbiased; that's an overstatement. Similarly, Lemma 4 minimizes an upper bound on the variance and then calls the result 'optimized.' That's a heuristic justification for PCA, not an optimality proof. The body is more careful than the abstract, but the abstract and conclusion oversell the guarantees.

The genuinely load-bearing issue is Lemma 5's failure probability guarantee. The quantile epsilon_d is calibrated in Eq. 14 on uniformly sampled data pairs. During search, the candidate pairs are conditioned on being close to the query, and the direction of the query-object difference has a different alignment with the PCA subspace than random pairs. The paper offers no evidence that the calibrated quantile holds on the actual candidate stream. Without that, the 'same level of accuracy' claim rests on the empirical recall curves, not on the stated theorem. This is fixable (e.g., measure the empirical tail probability on the candidate distribution), but it is the gap a referee should focus on.

Minor: there are no error bars or query-level variance numbers, which is common in ANNS papers but still worth noting. The reader's note about a missing code artifact is off; the abstract clearly links a repo.

Bottom line: this is a legitimate paper for the ANNS subfield, not a breakthrough. It deserves peer review. If the authors tighten the theoretical claims and address the calibration-transfer question, it would be a solid contribution. I'd bring it to our reading group if anyone is working on approximate nearest neighbor search.

Referee Report

3 major / 4 minor

Summary. The paper proposes DADE, a data-aware distance estimation method for distance comparison operations (DCOs) in approximate nearest neighbor search. DADE rotates the data with a PCA-derived orthogonal transformation, estimates distances in a low-dimensional subspace, and uses an adaptive hypothesis-testing procedure to decide when to expand the number of dimensions. The authors prove an unbiasedness identity for expected squared distances (Lemma 3), propose a variance-minimizing PCA-based estimator (Lemma 4), give a failure-probability bound (Lemma 5), and integrate the method into HNSW and IVF, reporting large QPS improvements over ADSampling while maintaining recall.

Significance. If the claims hold, DADE is a practically valuable plug-in component for graph-based and IVF-based ANNS indexes, and the paper provides a useful theoretical framework for data-aware DCO acceleration. The identity in Lemma 3 is correctly derived for expected squared distances of iid random pairs, and the experimental study covers six datasets and two index families with an artifact link. However, the advertised guarantees are weaker than stated: the unbiasedness is for squared distances of random pairs rather than for the fixed-pair decision used by the algorithm, the failure-probability bound depends on an unverified transfer of a calibration from uniform data pairs to conditioned candidate-query pairs, and the variance optimality is proved only for an upper bound. These issues are central to the paper's reliability claims and require substantial additional analysis or experiments.

major comments (3)

[Section 3.1, Lemma 3 and Algorithm 1] Lemma 3 establishes E[||X1-X2||^2] = (sigma^2(1,D)/sigma^2(1,d)) E[||W_d^T X1 - W_d^T X2||^2] for iid random pairs X1, X2. Algorithm 1, however, applies the square-rooted estimate to a single fixed pair (q,o) and uses it in a threshold decision. Jensen's inequality means that sqrt( (sigma^2(1,D)/sigma^2(1,d)) * ||W_d^T(q-o)||^2 ) is not an unbiased estimator of ||q-o||, and the expectation-level identity does not by itself control the probability of a wrong comparison for a fixed pair. The abstract's claim that the distance estimation is unbiased therefore needs to be qualified as unbiasedness of the squared distance in expectation over random pairs, and the reliability of the DCO decision needs a separate argument.
[Section 3.3, Eq. (14) and Lemma 5] The significance level P_s is used to calibrate epsilon_d through Eq. (14) on uniformly sampled data-object pairs, giving P(dis'/dis - 1 > epsilon_d) = P_s. During actual search, DCOs are applied to candidate-query pairs produced by the index, such as graph neighbors in HNSW or points in probed IVF clusters; these pairs are conditioned on proximity or other search properties and are not iid draws from the uniform data-pair distribution. Lemma 5's union bound in Eq. (16) is valid only if the calibrated tail bound transfers to the candidate stream. The paper provides no experiment comparing the calibrated epsilon_d with the empirical quantile on the actual candidate-query pairs, so the formal 'same accuracy' guarantee is unsupported. If the conditional tail exceeds P_s, the bound collapses and the algorithm can reject H0 with higher-than-claimed probability when dis <= r.
[Section 3.2, Lemma 4] Lemma 4 minimizes an upper bound on the variance, not the variance itself. The chain in Eq. (8) replaces tr(Sigma L_d Sigma L_d) with the larger quantity ||(L_d^{1/2})^H Sigma L_d^{1/2}||_F^2 and then with ||Sigma||_F^2 ||L_d^{1/2}||_F^4; Eq. (9) then minimizes that upper bound. Minimizing an upper bound does not in general minimize the original objective, and the proof does not show that the bound is tight for the data distributions of interest. The paper's contribution statement that the estimator is 'optimized in terms of variance' is stronger than what is proved; Lemma 4 itself says 'approximately achieved', but this caveat is not carried into the abstract or the contributions list.

minor comments (4)

[Algorithm 1] The increment d = d + Delta_d can overshoot D when D is not a multiple of Delta_d (e.g., Word2Vec with D=300 and Delta_d=32), after which the algorithm would use more than D dimensions. The pseudocode should cap d at D or otherwise handle the final partial step.
[Section 3.3, Eq. (14)] The displayed definition of dis' places the ratio outside the norm without a square root, making it an estimator of squared distance, yet Algorithm 1 and the surrounding text treat dis' as a distance. The formula should read dis' = sqrt( (sum_{k=1}^D lambda_k)/(sum_{k=1}^d lambda_k) ) * ||W_d^T(X1-X2)||.
[Section 4.1 and Section 5] There are several typographical errors, including 'ADSamping' for ADSampling in Section 4.1, 'hierachical' in Section 5, and 'experation' and 'addictivity' in the proof of Lemma 3.
[Figure 3] The x-axis of Figure 3 mixes absolute dimension counts and percentages, and the caption says 'recall-number of dimensions' while the axis is labeled '# of Dimensions/Lookups(%)'; please clarify the units and how the percentage is computed for each method.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: DADE's estimator and optimization are self-contained mathematical derivations, and the empirical calibration of the significance level is a validity assumption, not a fitted prediction.

full rationale

The paper's load-bearing claims are (1) an unbiased distance estimator in Eq. 13, (2) a variance-motivated choice of projection via PCA, and (3) an adaptive dimension-expansion rule with a failure-probability bound in Lemma 5. None of these reduces to its own inputs by construction. Lemma 3 and Eq. 13 are direct expectation identities under the stated i.i.d. and zero-mean assumptions; they do not assume the conclusion. Lemma 4 minimizes an upper bound on the estimation variance and explicitly labels the resulting objective as approximate; this is a stated relaxation, not a hidden re-use of the target result. The PCA solution is imported from a standard external reference, not from the authors' prior work. The hypothesis-testing rule calibrates the quantile epsilon_d so that the deviation probability equals P_s, and Lemma 5 then derives a union-bound failure probability from that calibration. This is a standard significance-level argument rather than a circular prediction: the recall improvements in the experiments are measured empirically, not derived from the calibrated quantile. The main caveat is that the calibration in Eq. 14 is performed on uniformly sampled data pairs while the DCOs during search face candidate pairs conditioned on proximity to the query; if that conditional distribution differs, the Lemma 5 bound need not hold in practice. That is a correctness or validity risk, not a circularity, because the paper does not claim to predict the conditioning effect from the calibration itself. Self-citations in the reference list are not load-bearing, and no uniqueness theorem or prior-work assumption is invoked to force the method. Accordingly, the circularity score is 0.

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

The central claim rests on the assumptions that data vectors are zero-mean iid draws from a fixed distribution, that the empirically calibrated error quantile epsilon_d transfers to search-conditioned candidate pairs, and that the surrogate-bound optimization in Lemma 4 controls the actual variance of the estimator. The main free parameters are the significance level P_s, the step size Delta_d, and the data-derived quantile epsilon_d.

free parameters (3)

P_s (significance level) = 0.1
Chosen empirically as a hyperparameter; the parameter study in Figure 4 varies P_s from 0.05 to 0.3, and the reported default is 0.1.
Delta_d (dimension expansion step) = 32
Set to 32 after parameter study (Figure 5); smaller steps increase hypothesis testing overhead, larger steps reduce accuracy.
epsilon_d(P_s, d) empirical error quantile = dataset-dependent, estimated from data objects
Defined in Eq 14 as the value such that P(dis'/dis - 1 > epsilon_d) = P_s, estimated by sampling data objects. This empirical calibration is what makes the failure probability bound in Lemma 5 hold, and it is a fitted quantity per dataset.

assumptions (4)

domain assumption Query and data vectors are iid draws from the same distribution (zero-mean after centering).
Used in Lemma 3 (Eq 3-4) to equate E[X^T W_d W_d^T X] with sum of variances and to justify unbiasedness; also assumed in the empirical calibration of Eq 14. The method subtracts the mean implicitly via PCA centering, but this is not stated in Algorithm 1.
domain assumption The empirical quantile epsilon_d estimated from uniformly sampled data pairs transfers to query-candidate pairs encountered during search.
Needed for Lemma 5's failure probability bound. Candidates in HNSW/IVF are conditioned on being near the query, so the relative error distribution may differ from the unconditional data-pair distribution.
domain assumption The orthogonal transformation W_D is exactly orthogonal and the data are centered before transformation.
The proofs of Lemmas 1-4 require W_D^T W_D = I and E[X] = 0; the implementation uses PCA on the empirical covariance but the centering step is not described in Algorithm 1.
ad hoc to paper The inequality in Eq 8, tr(Sigma L Sigma L) <= tr(|L^{1/2}|^H ... ), holds; used to replace the actual variance objective with a bound.
Lemma 4's proof of variance optimality depends on this inequality and on dropping E[||Delta X Delta X^T||_F^2] as a constant; the inequality is not proven and the bound relaxation means the proof only addresses a surrogate objective, not Eq 5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/2V6EMOIA

@misc{pith2026241117229,
  author       = {Pith},
  title        = {Pith review of: Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2V6EMOIA}},
  note         = {Machine review of arXiv:2411.17229}
}

abstract

High-dimensional approximate $K$ nearest neighbor search (AKNN) is a fundamental task for various applications, including information retrieval. Most existing algorithms for AKNN can be decomposed into two main components, i.e., candidate generation and distance comparison operations (DCOs). While different methods have unique ways of generating candidates, they all share the same DCO process. In this study, we focus on accelerating the process of DCOs that dominates the time cost in most existing AKNN algorithms. To achieve this, we propose an Data-Aware Distance Estimation approach, called DADE, which approximates the exact distance in a lower-dimensional space. We theoretically prove that the distance estimation in DADE is unbiased in terms of data distribution. Furthermore, we propose an optimized estimation based on the unbiased distance estimation formulation. In addition, we propose a hypothesis testing approach to adaptively determine the number of dimensions needed to estimate the exact distance with sufficient confidence. We integrate DADE into widely-used AKNN search algorithms, e.g., IVF and HNSW, and conduct extensive experiments to demonstrate the superiority.

Figures

Figures reproduced from arXiv: 2411.17229 by the authors.

**Figure 1.** Running Example on DEEP. (PCA), in which E[𝑋𝑋𝑇 ] is approximated by all data objects. Therefore, the solution for this problem can be obtained through matrix decomposition on E[𝑋𝑋𝑇 ], where 𝜆𝑘 is the 𝑘 largest eigenvalue and 𝑤𝑘 is the corresponding eigenvector. E[𝑋𝑋𝑇 ]𝑤𝑘 = 𝜆𝑘𝑤𝑘, 𝑓 𝑜𝑟 𝑘 = 1, 2, ..., 𝑑 (11) Moreover, we can also notice the following equation hold: Var(𝑤𝑘 𝑇𝑋 ) = E[𝑤𝑘 𝑇𝑋𝑋𝑇 𝑤𝑘 ] = 𝑤𝑘 𝑇 E[𝑋𝑋𝑇 ]𝑤𝑘 = 𝜆𝑘 (1… view at source ↗

**Figure 2.** Time-Recall Tradeoff. with C++. Following previous studies [20, 51], all hardware-specific optimizations including SIMD, and multi-threading are prohibited for a fair comparison. All C++ codes are complied by g++ 7.5.0 with −𝑂3 optimization and run in the platform with Ubuntu 16.04 operating system with 48-cores Intel(R) CPU E5-2650 v4 @ 2.20GHz 256GB RAM. Parameter Setting. For all HNSW-related approaches, two hype… view at source ↗

**Figure 3.** Feasibility for DCOs in terms of Recall and QPS. 80 85 90 95 100 Recall 100 200 300 400 500 600 QPS GIST, K=20, HNSW** P=0.05 P=0.1 P=0.15 P=0.2 P=0.25 P=0.3 70 80 90 100 Recall 100 200 300 400 500 QPS GIST, K=100, HNSW** 70 80 90 100 Recall 40 60 80 100 120 QPS GIST, K=20, IVF** 60 70 80 90 100 Recall 40 60 80 100 120 QPS GIST, K=100, IVF** [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Parameter Study on 𝑝 of AKNN** Algorithms with Different 𝐾. 80 85 90 95 100 Recall 100 200 300 400 500 600 QPS GIST, K=20, HNSW** d=1 d=2 d=4 d=8 d=16 d=32 d=64 70 80 90 100 Recall 100 200 300 400 500 QPS GIST, K=100, HNSW** 70 80 90 100 Recall 20 40 60 80 100 120 QPS …

**Figure 5.** Figure 5: Parameter Study on Δ𝑑 of AKNN** Algorithms with Different 𝐾. 4.2.2 Feasibility of Distance Estimation Methods for DCOs. Next, we study the feasibility of various distance estimations, i.e., Random Projection, PCA, ADSampling, and DADE. To eliminate the effect of differ…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 25 canonical work pages

[1]

Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HD- Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. Proceedings of the VLDB Endowment 11, 8 (2018)

work page 2018
[2]

Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. 2023. Tutorial Proposal: Retrieval-based Language Models and Applications. In The 61st Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts . 41

work page 2023
[3]

Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2023. Elpis: Graph-based similarity search for scalable data science. Proceedings of the VLDB Endowment 16, 6 (2023), 1548–1559

work page 2023
[4]

Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence 37, 6 (2014), 1247–1260

2014
[5]

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

Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517

1975
[7]

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

2006
[8]

Jin Chen, Zheng Liu, Xu Huang, Chenwang Wu, Qi Liu, Gangwei Jiang, Yuanhao Pu, Yuxuan Lei, Xiaolong Chen, Xingmei Wang, et al. 2024. When large language models meet personalization: Perspectives of challenges and opportunities.World Wide Web 27, 4 (2024), 42

2024

Show all 60 references

[9]

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. In Proceedings of the ACM Web Conference 2023 . 3225– 3235

2023
[10]

Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly-efficient billion-scale approximate nearest neighborhood search. Advances in Neural Information Processing Systems 34 (2021), 5199–5212

2021
[11]

Krzysztof M Choromanski, Mark Rowland, and Adrian Weller. 2017. The unrea- sonable effectiveness of structured random orthogonal embeddings. Advances in neural information processing systems 30 (2017)

2017
[12]

Paolo Ciaccia, Marco Patella, Pavel Zezula, et al. 1997. M-tree: An efficient access method for similarity search in metric spaces. InVldb, Vol. 97. Citeseer, 426–435

1997
[13]

Thomas Cover and Peter Hart. 1967. Nearest neighbor pattern classification. IEEE transactions on information theory 13, 1 (1967), 21–27

1967
[14]

Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 537–546

2008
[15]

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

2004
[16]

Liwei Deng, Hao Sun, Rui Sun, Yan Zhao, and Han Su. 2022. Efficient and effective similar subtrajectory search: a spatial-aware comprehension approach. TIST 13, 3 (2022), 1–22

2022
[17]

Liwei Deng, Yan Zhao, Jin Chen, Shuncheng Liu, Yuyang Xia, and Kai Zheng
[18]

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 Endowment 12, 5 (2019)

2019
[19]

Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In Proceedings of the 2012 ACM SIGMOD international conference on management of data . 541–552

2012
[20]

Jianyang Gao and Cheng Long. 2023. High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–27

2023
[21]

Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27

2024
[22]

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

2013
[23]

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

2018
[24]

Gaurav Gupta, Tharun Medini, Anshumali Shrivastava, and Alexander J Smola
[25]

Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data. 47–57

1984
[26]

Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giuseppe Ottaviano, and Linjun Yang. 2020. Embedding- based retrieval in facebook search. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &...

2020
[27]

Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355 (2018)

2018 arXiv
[28]

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 Processing Systems 32 (2019)

2019
[29]

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

2010
[30]

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

2019
[31]

Yannis Kalantidis and Yannis Avrithis. 2014. Locally optimized product quan- tization for approximate nearest neighbor search. In Proceedings of the IEEE conference on computer vision and pattern recognition . 2321–2328

2014
[32]

Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. 2020. Improving approximate nearest neighbor search through learned adaptive early termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2539–2554

2020
[33]

Hui Li, Tsz Nam Chan, Man Lung Yiu, and Nikos Mamoulis. 2017. FEXIPRO: fast and exact inner product retrieval in recommender systems. In Proceedings of the 2017 ACM International Conference on Management of Data . 835–850

2017
[34]

Nan Li, Bo Kang, and Tijl De Bie. 2023. SkillGPT: a RESTful API service for skill extraction and standardization using a Large Language Model. arXiv preprint arXiv:2304.11060 (2023)

2023 arXiv
[35]

Defu Lian, Yongji Wu, Yong Ge, Xing Xie, and Enhong Chen. 2020. Geography- aware sequential location recommendation. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining . 2009– 2019

2020
[36]

Yingfan Liu, Hong Cheng, and Jiangtao Cui. 2017. PQBF: i/o-efficient approximate nearest neighbor search by product quantization. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management . 667–676

2017
[37]

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 Endowment 15, 2 (2021), 246– 258

2021
[38]

Zepu Lu, Jin Chen, Defu Lian, Zaixi Zhang, Yong Ge, and Enhong Chen. 2024. Knowledge distillation for high dimensional search index. Advances in Neural Information Processing Systems 36 (2024)

2024
[39]

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 intelligence 42, 4 (2018), 824–836

2018
[40]

Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 2227–2240

2014
[41]

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

Shumpei Okura, Yukihiro Tagami, Shingo Ono, and Akira Tajima. 2017. Embedding-based news recommendation for millions of users. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 1933–1942

2017
[43]

Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27

2023
[44]

Shashank Rajput, Nikhil Mehta, Anima Singh, Raghunandan Hulikal Keshavan, Trung Vu, Lukasz Heldt, Lichan Hong, Yi Tay, Vinh Tran, Jonah Samost, et al
[45]

Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. Proceedings of the VLDB Endowment (2014)

2014
[46]

Yao Tian, Xi Zhao, and Xiaofang Zhou. 2023. DB-LSH 2.0: Locality-sensitive hashing with query-based dynamic bucketing. IEEE Transactions on Knowledge and Data Engineering (2023). 9

2023
[47]

Ingo Wald and Vlastimil Havran. 2006. On building fast kd-trees for ray tracing, and on doing that in O (N log N). In 2006 IEEE Symposium on Interactive Ray Tracing. IEEE, 61–69

2006
[48]

Hao Wang, Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du, Han Wu, and Wen Su. 2019. MCNE: An end-to-end framework for learning multiple conditional network representations of social network. In Proceedings of the 25th ACM SIGKDD international conference on knowledge disc...

2019
[49]

Advances in Neural Information Processing Systems 36 (2024)

Recommender systems with generative retrieval. Advances in Neural Information Processing Systems 36 (2024)

2024
[50]

Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xi- angyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High- Dimensional Vector Similarity Search on Data Segment. Proceed...

2024
[51]

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 Endowment 14, 11 (2021), 1964–1978

2021
[52]

Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards efficient index construction and approximate nearest neighbor search in high- dimensional spaces. Proceedings of the VLDB Endowment 16, 8 (2023), 1979–1991

2023
[53]

Bolong Zheng, Zhao Xi, Lianggui Weng, Nguyen Quoc Viet Hung, Hang Liu, and Christian S Jensen. 2020. PM-LSH: A fast and accurate LSH framework for high-dimensional approximate NN search. Proceedings of the VLDB Endowment 13, 5 (2020), 643–655

2020
[54]

Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. 2017. A survey on learning to hash. IEEE transactions on pattern analysis and machine intelligence 40, 4 (2017), 769–790

2017
[55]

Zhi-Hua Zhou. 2021. Machine learning. Springer nature. 10

2021
[59]

Bolong Zheng, Ziyang Yue, Qi Hu, Xiaomeng Yi, Xiaofan Luan, Charles Xie, Xiao- fang Zhou, and Christian S Jensen. 2023. Learned probing cardinality estimation for high-dimensional approximate NN search. In 2023 IEEE 39th International Conference on Data Engineering (ICDE) . IE...

2023
[1990]

In Proceedings of the 1990 ACM SIGMOD international conference on Management of data

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

1990
[2019]

Pattern Recognition 96 (2019), 106970

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

2019
[2022]

In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Bliss: A billion scale index using iterative re-partitioning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . 486–495
[2024]

Learning to Hash for Trajectory Similarity Computation and Search. In ICDE. IEEE, 4491–4503

Pith tools

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

[1] [1]

Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HD- Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. Proceedings of the VLDB Endowment 11, 8 (2018)

work page 2018

[2] [2]

Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. 2023. Tutorial Proposal: Retrieval-based Language Models and Applications. In The 61st Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts . 41

work page 2023

[3] [3]

Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2023. Elpis: Graph-based similarity search for scalable data science. Proceedings of the VLDB Endowment 16, 6 (2023), 1548–1559

work page 2023

[4] [4]

Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence 37, 6 (2014), 1247–1260

2014

[5] [5]

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

[6] [6]

Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517

1975

[7] [7]

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

2006

[8] [8]

Jin Chen, Zheng Liu, Xu Huang, Chenwang Wu, Qi Liu, Gangwei Jiang, Yuanhao Pu, Yuxuan Lei, Xiaolong Chen, Xingmei Wang, et al. 2024. When large language models meet personalization: Perspectives of challenges and opportunities.World Wide Web 27, 4 (2024), 42

2024