Pith. sign in

REVIEW 4 major objections 6 minor 47 references

On the Merge of k-NN Graph

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Merging two approximate k-NN graphs can be done for about one-third of the from-scratch construction cost, while keeping graph recall within 3% of building the whole graph with NN-Descent.

desk verdict Solid empirical contribution on a genuinely unaddressed problem—k-NN graph merging—with a real but untested distribution-shift caveat and a shaky complexity derivation. read the letter →

arxiv 1908.00814 v6 pith:FA3Q6EQL submitted 2019-08-02 cs.IR cs.DScs.LG

Wan-Lei Zhao , Hui Wang , Peng-Cheng Lin , Chong-Wah Ngo This is my paper · ORCID
classification cs.IRcs.DScs.LG
keywords k-nearestneighborgraphmergingNN-Descenthierarchicalnearestsearchincrementalconstructionapproximatek-NNhill-climbing
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

Two approximate nearest-neighbor graphs can be fused without rebuilding the whole graph. This paper introduces S-Merge, which combines two existing k-NN graphs, and J-Merge, which absorbs a raw batch into an existing graph; both work by seeding each neighborhood list with random samples from the other side and then running the standard “neighbor’s neighbor” hill-climbing update restricted to cross-set pairs. The claimed payoff is a distance-computation cost around one-third (S-Merge) and two-thirds (J-Merge) of building the graph from scratch with NN-Descent, while keeping graph recall within 3% of NN-Descent. Because J-Merge handles raw batches, it also yields an incremental, hierarchical construction (H-Merge) whose top layers act as shortcuts for nearest-neighbor search. A sympathetic reader would care because this turns graph merging from an overlooked, apparently costly operation into a building block for parallel and streaming approximate graph construction.

What carries the argument

The load-bearing mechanism is the half-baked seed graph plus a restricted NN-Descent loop. Concretely, each k-NN list is truncated to $k/2$ entries and seeded with $k/2$ uniformly random samples from the other dataset, so the initial graph already contains enough cross-set edges for hill-climbing; the loop then uses the “neighbor’s neighbor is likely a neighbor” rule but only evaluates pairs that cross the $S_1/S_2$ boundary (S-Merge) or that cross the boundary or lie inside the raw set (J-Merge). Convergence is carried by the potential $\varphi(G)$, the sum over all samples of all listed neighbor distances, which decreases monotonically on every accepted swap and is bounded below by the true k-NN graph’s sum; because the state space is finite, the loop must stop. The complexity ratios (one-third and two-thirds of NN-Descent) follow from the assumption that random seeding mixes the two sides so thoroughly that roughly one-third and two-thirds of all distance comparisons in the from-scratch run are retained.

What would settle it

Construct a dataset from two well-separated Gaussian clusters, build a k-NN graph on one cluster and try to merge in the other cluster with S-Merge or J-Merge; if recall@10 on the merged graph falls far below the within-3% gap that the paper reports for random splits, the same-distribution assumption is violated. A simpler version: split MNIST into digit 0-4 and digit 5-9 and compare merge recall against NN-Descent on the full set.

Watch

Extended reading notes

Core claim

On the paper’s own terms, the central claim is that merging two approximate k-NN graphs is not a separate hard problem: it is NN-Descent starting halfway up the hill. S-Merge cuts the rear half off each NN list, appends $k/2$ uniformly random samples from the other subgraph, and iterates NN-Descent while comparing only samples that come from different sides; J-Merge does the same when one side is raw, initializing the raw samples’ lists from the union and also comparing within the raw set. Both end by merging the truncated rear lists back with a merge sort. The paper derives, from a monotone potential $\varphi(G)$ that sums all listed neighbor distances, that the iteration converges, and argues from random mixing that S-Merge performs about one-third and J-Merge about two-thirds of the distance computations of constructing the whole graph from scratch. It reports recall within 3% of NN-Descent on synthetic and real datasets under $\ell_1$, $\ell_2$, cosine, $\chi^2$, and Jaccard distances. Applying J-Merge to successively doubled random batches gives H-Merge, a hierarchy of approximate k-NN graphs whose top-down NN search is competitive with HNSW, with the extra property that every layer remains a true approximate k-NN graph.

Load-bearing premise

The load-bearing premise is that the two datasets to be merged are random samples of the same underlying distribution, so that $k/2$ uniformly random cross-set links per list are enough for the hill-climbing loop to discover the true cross-set edges; if a batch comes from a different distribution, the random seeds miss the close pairs and the merge quality collapses.

Editorial extensions

If this is right

  • Parallel construction of a k-NN graph can be done by building subgraphs independently and repeatedly applying S-Merge, rather than rebuilding on the union.
  • A k-NN graph over a streaming collection can be maintained incrementally: each new batch is absorbed by J-Merge at a fraction of the from-scratch cost, without ever needing all data in memory at once.
  • The H-Merge hierarchy supplies a nearest-neighbor index whose upper layers are coarse approximate k-NN graphs, so search can skip large portions of the data in low intrinsic dimension.
  • Because every layer of H-Merge remains an approximate k-NN graph, the same structure supports neighbor browsing tasks that HNSW-style sparsified graphs do not support.
  • The merge operations inherit NN-Descent’s generality across distance measures, so the cost savings extend to non-Euclidean metrics such as cosine, $\chi^2$, and Jaccard.

Reading between the lines

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

  • Beyond the paper: the merge cost model assumes the two sides are random samples of one distribution. If a new batch arrives from a shifted distribution, random cross-set seeds may contain no close pairs, and the restricted hill-climb cannot recover them; a testable fix would seed cross-set links by a cheap retrieval step, such as coarse hashing, before the NN-Descent loop.
  • Beyond the paper: the one-third/two-thirds arithmetic suggests the same merge idea could be applied recursively to more than two graphs with a composition law; whether multi-way merging in one pass beats pairwise recursive merging is not addressed and could be measured as an extension.
  • Beyond the paper: H-Merge’s hierarchy sizes were fixed as a hyperparameter (e.g., 64, 512, and so on); choosing layer sizes adaptively from the data’s intrinsic dimension might further improve the search speed/recall trade-off, since the paper’s own results show the hierarchy helps most when intrinsic dimension is low.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. This paper addresses the problem of merging approximate k-NN graphs, which has received little prior attention. Two algorithms are proposed: S-Merge, which merges two already-built k-NN graphs, and J-Merge, which merges a raw data batch into an existing graph. Both algorithms initialize each neighborhood list with a random half of samples from the other set and then run NN-Descent-style hill climbing, restricted in S-Merge to cross-set comparisons. Repeated J-Merge yields H-Merge, a hierarchical k-NN graph construction used for fast NN search. The paper reports that merge quality is within 3% of NN-Descent while scanning rates are about one-third and two-thirds of NN-Descent, and that H-Merge is competitive with HNSW on a broad set of datasets. A convergence argument and complexity analysis are given in Section 3.4, and experiments cover synthetic and real data with multiple distance measures.

Significance. If the results hold, the paper fills a genuine gap: k-NN graph merging enables parallel and incremental construction without rebuilding the graph from scratch. The empirical evaluation is broad, covering six synthetic and ten real-world datasets, several distance measures, and up to 10M points, and the authors state that the code is open-sourced, which supports reproducibility. The H-Merge search results are competitive with HNSW while preserving a full k-NN graph at each layer, a property useful for applications that need neighbor browsing as well as search. However, the paper's central cost claims rest on a complexity derivation that is internally inconsistent, and the merge-quality claim is demonstrated only for random splits of a single dataset. The contribution is valuable, but the theoretical arguments and the stated scope need significant revision.

major comments (4)
  1. [Sec. 3.4, Eq. (3)] The 'one-third' cross-comparison fraction is not supported by the algorithm's own initialization. In S-Merge, after Step 1 each NN list has k/2 samples from S1 and k/2 samples from S2; the fraction of unordered cross-set pairs among the k entries is approximately (k/2)^2 / C(k,2) ~ 1/2, not 1/3. Since Eq. (3) is the basis for the headline 'one-third of NN-Descent cost' claim and for Table 1, the derivation should be reworked or replaced by a direct empirical measurement of the cross-comparison fraction.
  2. [Sec. 3.4, Table 1 (H-Merge)] The stated O(5 d n^ρ /3) complexity for H-Merge does not follow from the preceding text. If each level of the doubling hierarchy costs J-Merge's stated 2/3 d m^ρ, the geometric sum over m = n/2, n/4, ... gives approximately (2/3)/(1 - 2^{-ρ}) d n^ρ, which for ρ in [1.4, 1.9] is about 0.9–1.03 d n^ρ, not 5/3. The sentence claiming 'roughly 1.67 times' needs an explicit calculation identifying which operations contribute the extra constant.
  3. [Secs. 3.1–3.3, 5.2] The central merge-quality claim is established only for randomly split data. In Alg. 1 (lines 4–7) and Alg. 2 (lines 3–6), the only cross-set edges available to hill climbing are the k/2 random cross-set links seeded per list. All experiments in Sec. 5.2 divide each dataset randomly, so every local neighborhood contains both subsets with the same density. The paper motivates merging with streaming data (Sec. 1), where a new batch can follow a different distribution; in that case the random seeds may all lie far from the true cross-set neighbors, and the iterative comparisons cannot recover the missing edges. Please test non-i.i.d. partitions, such as batches drawn from different clusters or temporally shifted data, or narrow the claimed scope of S-Merge and J-Merge.
  4. [Sec. 5.2, Table 3] The scanning rates reported for S-Merge and J-Merge exclude the cost of building the input subgraphs, so the comparison against from-scratch NN-Descent is not end-to-end. For |S1| = |S2|, constructing the two subgraphs by NN-Descent adds roughly 2 d (n/2)^ρ distance computations, which partially or fully offsets the merge savings. The text's caveat in Sec. 5.2.2 acknowledges this only indirectly; the headline 'one-third / two-thirds of NN-Descent' should be presented with a full cost accounting.
minor comments (6)
  1. [Alg. 2, Line 6] The initialization 'Initialize G2[i] with k random samples from S1∪S2' can select the sample itself; the paper should state that self-edges are excluded, as is standard in k-NN graph construction.
  2. [Sec. 5.2.2] The sentence 'S-Merge actually shows slightly higher scanning rates than J-Merge...' is ambiguous because 'higher scanning rate' could be read as better quality; clarify that it means more distance computations.
  3. [Sec. 3.3] The requirement that each subset joined into the hierarchy be randomly drawn from the whole set is stated as an assumption, but it is not listed among the limitations in Secs. 1 or 5; the paper should state explicitly that the merge algorithms preserve quality only under this representativeness assumption.
  4. [Sec. 5.3.1, Table 4] The statement that H-Merge takes 'roughly twice more' time than NN-Descent is inconsistent with RAND10M8D (597.07 s vs. 132.84 s, a factor of about 4.5); either the sentence should be qualified by dataset or the discrepancy explained.
  5. [Eq. (7)] The scanning rate c is defined with C as the total number of distance computations; please state explicitly whether C in Table 3 includes the distance computations spent in building the input subgraphs for S-Merge and J-Merge.
  6. [Fig. 5] The caption of Fig. 5 contains the typo 'SIFT1HKMNIST'; it should read 'SIFT100K, MNIST'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation chain: the merge algorithms are empirical extensions of NN-Descent, parameter r is selected by ablation, and the complexity analysis relies on an external exponent from [5].

full rationale

The paper's central claims are empirical: S-Merge/J-Merge recall and cost are compared with NN-Descent [5], NN-Descent*, NSW, RLB, HNSW, and other baselines, and the measured recall differences are not manufactured by a fitted constant. The truncation ratio r is selected by ablation in Sec. 5.2.1 and fixed at 1/2; the subsequent recall numbers are outputs of the algorithms, not re-statements of the ablation choice. Complexity bounds in Sec. 3.4 (Eqs. 3-4, Tab. 1) use the external empirical exponent rho from [5] plus a mixing assumption, and are approximate analyses rather than definitions of the reported quality. Self-citations [32] and [47] occur only as related-work comparisons, not as load-bearing justifications, and [47] is corroborated by the external citation [31]. The random-draw requirement for H-Merge in Sec. 3.3 is an untested assumption that limits the stated scope under distribution shift, but it is a correctness and generalization concern, not a circular step, because the paper's equations do not define its target graph quality in terms of that assumption. No evidence was found that any prediction or claimed result reduces by construction to its inputs.

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

The central efficiency and quality claims rest on the random-seeding heuristic inherited from NN-Descent and on the assumption that subsets are exchangeable random splits. The only tuned parameter is r (set to 1/2); the layer sizes are experimental configuration. No derived constants are fitted to target results, but the complexity formulas lean on empirical rho from [5].

free parameters (2)
  • truncation ratio r = 1/2
    Determines how many neighbors are retained (top r*k) versus replaced by random samples from the other set; chosen after ablation on RAND100K100D (Sec. 5.2.1) and then fixed for all datasets.
  • H-Merge layer sizes = 64, 512, 4096, 32768, n
    Fixed hierarchy sizes used in search experiments (Sec. 5.3); not derived from data, and the paper says arbitrary layers may be saved.
assumptions (4)
  • domain assumption The 'neighbor's neighbor is likely to be the neighbor' heuristic holds across the S1/S2 boundary for random subsets.
    Underlies NN-Descent and the merge algorithms; if false, cross-set comparisons in a mixed list do not reveal true neighbors. Invoked in Alg. 1 and Alg. 2.
  • domain assumption Two subsets to be merged are random samples from the same underlying distribution.
    Required for random cross-set initialization to seed useful comparisons; experiments always split datasets randomly. See Sec. 3.3.
  • domain assumption Empirical complexity exponent rho in [1.4, 1.9] for NN-Descent.
    Used in the time-complexity formulas of Sec. 3.4; taken from the authors' empirical study [5], not derived in this paper.
  • standard math Monotone decrease of phi(G) implies convergence of the batch hill-climbing updates.
    Finite state space plus strict decrease of the sum-of-distances objective; valid as a convergence argument but does not establish optimality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Merge of k-NN Graph." pith.science (2026). https://pith.science/paper/FA3Q6EQL

@misc{pith2026190800814,
  author       = {Pith},
  title        = {Pith review of: On the Merge of k-NN Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FA3Q6EQL}},
  note         = {Machine review of arXiv:1908.00814}
}
read the original abstract

k-nearest neighbor graph is a fundamental data structure in many disciplines such as information retrieval, data-mining, pattern recognition, and machine learning, etc. In the literature, considerable research has been focusing on how to efficiently build an approximate k-nearest neighbor graph (k-NN graph) for a fixed dataset. Unfortunately, a closely related issue of how to merge two existing k-NN graphs has been overlooked. In this paper, we address the issue of k-NN graph merging in two different scenarios. In the first scenario, a symmetric merge algorithm is proposed to combine two approximate k-NN graphs. The algorithm facilitates large-scale processing by the efficient merging of k-NN graphs that are produced in parallel. In the second scenario, a joint merge algorithm is proposed to expand an existing k-NN graph with a raw dataset. The algorithm enables the incremental construction of a hierarchical approximate k-NN graph. Superior performance is attained when leveraging the hierarchy for NN search of various data types, dimensionality, and distance measures.

Figures

Figures reproduced from arXiv: 1908.00814 by the authors.

Figure 1
Figure 1. The illustration of symmetric merge (S-Merge). Figure (a) shows two disconnected subgraphs. For distinction, the [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The illustration of the heuristic strategy used to [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 4
Figure 4. The fluctuation trend of graph quality when varying [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figures from the paper (4 more)
Figure 6
Figure 6. Figure 6: The efficiency of S-Merge and J-Merge in comparison [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 5
Figure 5. Figure 5: The quality of approximate k-NN graphs produced by S-Merge and J-Merge, in comparison to NN-Descent, NSW and RLB on six synthetic datasets and four real-world datasets. On the synthetic datasets, both l1-norm and l2- norm are tested. On all the runs for S-Merge and J-M…
Figure 7
Figure 7. Figure 7: The NN search performance from representative graph-based approaches on ten datasets. The performance is given [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: The performance of H-Merge in comparison to rep [PITH_FULL_IMAGE:figures/full_fig_p013_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 45 canonical work pages

  1. [1]

    A global geometric framework for nonlinear dimensionality reduction,

    J. B. Tenenbaum, V . de Silva, and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction,” Science, vol. 5500, pp. 2319–2323, Dec. 2000

    work page 2000

  2. [2]

    Report nonlinear dimensionality re- duction by locally linear embedding,

    S. T. Roweis and L. K. Saul, “Report nonlinear dimensionality re- duction by locally linear embedding,” Science, vol. 5500, pp. 2323– 2326, Dec. 2000

    work page 2000

  3. [3]

    A survey on large- scale machine learning,

    M. Wang, W. Fu, X. He, S. Hao, and X. Wu, “A survey on large- scale machine learning,” IEEE Transactions on Knowledge and Data Engineering, pp. 1–1, 2020

    work page 2020

  4. [4]

    Fast graph construction using auction algo- rithm,

    J. Wang and Y. Xia, “Fast graph construction using auction algo- rithm,” in Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, 2012

    work page 2012

  5. [5]

    Efficient k-nearest neighbor graph construction for generic similarity measures,

    W. Dong, C. Moses, and K. Li, “Efficient k-nearest neighbor graph construction for generic similarity measures,” in Proceedings of the 20th International Conference on World Wide Web , WWW’11, (New York, NY, USA), pp. 577–586, ACM, 2011

    work page 2011

  6. [6]

    EFANNA : An extremely fast approximate nearest neighbor search algorithm based on knn graph,

    C. Fu and D. Cai, “EFANNA : An extremely fast approximate nearest neighbor search algorithm based on knn graph,” arXiv.org,

    work page

  7. [7]

    Fast approximate knn graph construction for high dimensional data via recursive lanczos bisec- tion,

    J. Chen, H. ren Fang, and Yousef, “Fast approximate knn graph construction for high dimensional data via recursive lanczos bisec- tion,” Journal of Machine Learning Research , vol. 10, pp. 1989–2012, Dec. 2009

    work page 1989

  8. [8]

    Scalable k-nn graph construction for visual descriptors,

    J. Wang, J. Wang, G. Zeng, Z. Tu, R. Gan, and S. Li, “Scalable k-nn graph construction for visual descriptors,” in CVPR, pp. 1106– 1113, Jun. 2012

    work page 2012

Show all 47 references
  1. [9]

    Fast knn graph construction with locality sensitive hashing,

    Y.-M. Zhang, K. Huang, G. Geng, and C.-L. Liu, “Fast knn graph construction with locality sensitive hashing,” in Proceedings of the 2013th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part II , ECMLPKDD’13, pp. 660– 674, Springer-Verlag, 2013

    2013

  2. [10]

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

    K. Hajebi, Y. Abbasi-Yadkor, H. Shahbazi, and H. Zhang, “Fast approximate nearest-neighbor search with k-nearest neighbor graph,” in International Joint Conference on Artificial Intelligence , pp. 1312–1317, 2011

    2011

  3. [11]

    Being prepared in a sparse world: the case of KNN graph construction,

    A. Boutet, A.-M. Kermarrec, N. Mittal, and F. Taiani, “Being prepared in a sparse world: the case of KNN graph construction,” in Proceedings of the 32th IEEE International Conference on Data Engineering, pp. 241–252, IEEE, 2016

    2016

  4. [12]

    Ap- proximate nearest neighbor algorithm based on navigable small world graphs,

    Y. A. Malkov, A. Ponomarenko, A. Lovinov, and V . Krylov, “Ap- proximate nearest neighbor algorithm based on navigable small world graphs,” Information Systems, 2013

    2013

  5. [13]

    Efficient and robust approx- imate nearest neighbor search using hierarchical navigable small world graphs,

    Y. A. Malkov and D. A. Yashunin, “Efficient and robust approx- imate nearest neighbor search using hierarchical navigable small world graphs,” Trans. P AMI, pp. 1–1, 2018

    2018

  6. [14]

    Multidimensional binary search trees used for as- sociative searching,

    J. L. Bentley, “Multidimensional binary search trees used for as- sociative searching,” Communications of the ACM, vol. 18, pp. 509– 517, Sep. 1975

    1975

  7. [15]

    R-trees: A dynamic index structure for spatial searching,

    A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proceedings of the 1984 ACM SIGMOD international conference on Management of data , vol. 14, (New York, NY, USA), pp. 47–57, ACM, Jun. 1984

    1984

  8. [16]

    The x-tree : An index structure for high-dimensional data,

    S. Berchtold, D. A. Keim, and H.-P . Kriegel, “The x-tree : An index structure for high-dimensional data,” in Proceedings of the 22th International Conference on Very Large Data Bases , pp. 28–39, Sep. 1996

    1996

  9. [17]

    NV- tree: An efficient disk-based index for approximate search in very large high-dimensional collections,

    H. Lejsek, F.-H. Asmundsson, B. B. Jonsson, and L. Amsaleg, “NV- tree: An efficient disk-based index for approximate search in very large high-dimensional collections,” IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 869–883, May 2009

    2009

  10. [18]

    Trinary-projection trees for approximate nearest neighbor search,

    J. Wang, N. Wang, Y. Jia, J. Li, G. Zeng, H. Zha, and X.-S. Hua, “Trinary-projection trees for approximate nearest neighbor search,” Trans. P AMI, vol. 36, no. 2, pp. 388–403, 2014

    2014

  11. [19]

    Scalable nearest neighbor algorithms for high dimensional data,

    M. Muja and D. G. Lowe, “Scalable nearest neighbor algorithms for high dimensional data,” Trans. P AMI, vol. 36, pp. 2227–2240, 2014

    2014

  12. [20]

    Optimised kd-trees for fast image descriptor matching,

    C. Silpa-Anan and R. Hartley, “Optimised kd-trees for fast image descriptor matching,” in CVPR, 2008

    2008

  13. [21]

    Approximate nearest neighbor search by residual vector quantization,

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

    2010

  14. [22]

    Product quantization for nearest neighbor search,

    H. J ´egou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” Trans. P AMI, vol. 33, pp. 117–128, Jan. 2011

    2011

  15. [23]

    Efficient indexing of billion-scale datasets of deep descriptors,

    A. Babenko and V . Lempitsky, “Efficient indexing of billion-scale datasets of deep descriptors,” in CVPR, pp. 2055–2063, 2016

    2016

  16. [24]

    Composite quantization for ap- proximate nearest neighbor search,

    T. Zhang, C. Du, and J. Wang, “Composite quantization for ap- proximate nearest neighbor search,” in ICML, pp. 838–846, 2014

    2014

  17. [25]

    Locality- sensitive hashing scheme based on p-stable distributions,

    M. Datar, N. Immorlica, P . Indyk, and V . S. Mirrokni, “Locality- sensitive hashing scheme based on p-stable distributions,” in Proceedings of the Twentieth Annual Symposium on Computational Geometry, (New York, NY, USA), pp. 253–262, ACM, 2004

    2004

  18. [26]

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

    Q. Lv, W. Josephson, Z. Wang, and M. C. amd Kai Li, “Multi-probe lsh: Efficient indexing for high-dimensional similarity search,” in Proceedings of Very Large Data bases, Sep. 2007

    2007

  19. [27]

    Supervised hashing with kernels,

    W. Liu, J. Wang, R. Ji, Y. G. Jiang, and S. F. Chang, “Supervised hashing with kernels,” in CVPR, 2012

    2012

  20. [28]

    Locality- sensitive hashing scheme based on p-stable distributions,

    M. Datar, P . Indyk, N. Immorlica, and V . S. Mirrokni, “Locality- sensitive hashing scheme based on p-stable distributions,” in Twentieth Symposium on Computational Geometry, 2004

    2004

  21. [29]

    A survey on learning to hash,

    J. Wang, T. Zhang, J. Song, N. Sebe, and H. T. Shen, “A survey on learning to hash,” Trans. P AMI, vol. 40, no. 4, pp. 769–790, 2018

    2018

  22. [30]

    Query-driven iterated neighborhood graph search for large scale indexing,

    J. Wang and S. Li, “Query-driven iterated neighborhood graph search for large scale indexing,” in Proceedings of the 20th ACM International Conference on Multimedia , (New York, NY, USA), pp. 179–188, ACM, 2012

    2012

  23. [31]

    Ap- proximate nearest neighbor search on high dimensional data- experiments, analysis and improvement,

    W. Li, Y. Zhang, Y. Sun, W. Wang, W. Zhang, and X. Lin, “Ap- proximate nearest neighbor search on high dimensional data- experiments, analysis and improvement,” IEEE Transactions on Knowledge and Data Engineering, pp. 1–1, 2019

    2019

  24. [32]

    k-NN graph construction: a generic online approach,

    W.-L. Zhao, “k-NN graph construction: a generic online approach,” Arxiv.org, vol. abs/1804.03032, 2018. https://arxiv.org/abs/1804.03032

    2018 arXiv

  25. [33]

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

    C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,” in The Proceedings of the VLDB Endowment, vol. 12, pp. 461–474, Jan. 2019

    2019

  26. [34]

    Hierarchical clustering-based graphs for large scale approximate 15 nearest neighbor search,

    J. V . Mu ˜noz, M. A. Gonc ¸alves, Z. Dias, and R. da S. Torres, “Hierarchical clustering-based graphs for large scale approximate 15 nearest neighbor search,” Pattern Recognition , vol. 96, p. 106970, 2019

    2019

  27. [35]

    FANNG: Fast approximate near- est neighbour graphs,

    B. Harwood and T. Drummond, “FANNG: Fast approximate near- est neighbour graphs,” in CVPR, pp. 5713–5722, 2016

    2016

  28. [36]

    Maximum likelihood estimation of intrinsic dimension,

    E. Levina and P . J. Bickel, “Maximum likelihood estimation of intrinsic dimension,” Advances in Neural Information Processing Systems, 2005

    2005

  29. [37]

    Distinctive image features from scale-invariant key- points,

    D. G. Lowe, “Distinctive image features from scale-invariant key- points,” International Journal on Computer Vision , vol. 60, no. 2, pp. 91–110, 2004

    2004

  30. [38]

    ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms,

    A. F. Martin Aum ¨uller, Erik Bernhardsson, “ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms,” 2019

    2019

  31. [39]

    Video google: A text retrieval approach to object matching in videos,

    J. Sivic and A. Zisserman, “Video google: A text retrieval approach to object matching in videos,” in ICCV, pp. 1470–1477, 2003

    2003

  32. [40]

    Evaluation of GIST descriptors for web-scale image search,

    M. Douze, H. J ´egou, H. Singh, L. Amsaleg, and C. Schmid, “Evaluation of GIST descriptors for web-scale image search,” in CIVR, pp. 19:1–19:8, Jul. 2009

    2009

  33. [41]

    Glove: Global vectors for word representation,

    J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in Empirical Methods in Natural Language Processing (EMNLP), pp. 1532–1543, 2014

    2014

  34. [42]

    YFCC100M hybridnet fc6 deep features for content-based image retrieval,

    G. Amato, F. Falchi, C. Gennaro, and F. Rabitti, “YFCC100M hybridnet fc6 deep features for content-based image retrieval,” in Proceedings of the 2016 ACM Workshop on Multimedia COMMONS , pp. 11–18, 2016

    2016

  35. [43]

    Q. Chen, H. Wang, M. Li, G. Ren, S. Li, J. Zhu, J. Li, C. Liu, L. Zhang, and J. Wang, SPTAG: A library for fast approximate nearest neighbor search, 2018

    2018

  36. [44]

    SRS: solving c-approximate nearest neighbor queries in high dimensional eu- clidean space with a tiny,

    Y. Sun, W. Wang, J. Qin, Y. Zhang, and X. Lin, “SRS: solving c-approximate nearest neighbor queries in high dimensional eu- clidean space with a tiny,” in The Proceedings of the VLDB Endow- ment, pp. 1–12, Sep. 2014

    2014

  37. [45]

    Annoy: approximate nearest neighbors in C++/Python optimized for memory usage and loading/saving to disk,

    E. Bernhardsson, “Annoy: approximate nearest neighbors in C++/Python optimized for memory usage and loading/saving to disk,” 2016

    2016

  38. [46]

    OpenMP: open multiprocessing

    “OpenMP: open multiprocessing.” https://www.openmp.org/

  39. [47]

    Graph based nearest neighbor search: Promises and failures,

    P . C. Lin and W. L. Zhao, “Graph based nearest neighbor search: Promises and failures,” arXiv.org, 2019. https://arxiv.org/abs/1904.02077. Wan-Lei Zhao received his Ph.D degree from City University of Hong Kong in 2010. He re- ceived M.Eng. and B.Eng. degrees in Depart- ment ...

    2019 arXiv

Pith tools

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