Pith. sign in

REVIEW 3 cited by

Graph based Nearest Neighbor Search: Promises and Failures

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1904.02077 v5 pith:ACEZDFKR submitted 2019-04-03 cs.IR cs.CVcs.DScs.MMcs.SI

Peng-Cheng Lin , Wan-Lei Zhao This is my paper · ORCID
classification cs.IRcs.CVcs.DScs.MMcs.SI
keywords graphsearchapproacheshierarchicalnearestneighborstructurediversification
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Recently, graph based nearest neighbor search gets more and more popular on large-scale retrieval tasks. The attractiveness of this type of approaches lies in its superior performance over most of the known nearest neighbor search approaches as well as its genericness to various metrics. In this paper, the role of two strategies, namely hierarchical structure and graph diversification that are adopted as the key steps in the graph based approaches, is investigated. We find the hierarchical structure could not achieve "much better logarithmic complexity scaling" as it was claimed in the original paper, particularly on high dimensional cases. Moreover, we find that similar high search speed efficiency as the one with hierarchical structure could be achieved with the support of flat k-NN graph after graph diversification. Finally, we point out the difficulty, that is faced by most of the graph based search approaches, is directly linked to "curse of dimensionality".

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval

    cs.IR 2026-07 conditional novelty 6.0 of 10

    crEG, an even-regular undirected proximity graph with continuous edge refinement, matches or beats HNSW/NSG/ONNG in standard and exploratory query settings while building 2-3x faster.

  2. Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art

    cs.IR 2025-02 conditional novelty 6.0 of 10

    An evaluation of twelve graph-based vector search methods on up to one billion vectors shows that incremental insertion and neighborhood diversification are the design choices that scale best.

  3. Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization

    cs.LG 2025-01 conditional novelty 4.0 of 10

    HNSW++ modifies HNSW with a dual-branch graph, LID-based insertion, and skip bridges, reporting better recall and construction speed on six small datasets.

Pith tools