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.
Graph based Nearest Neighbor Search: Promises and Failures
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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".
citation-role summary
background 1
citation-polarity summary
fields
cs.IR 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art
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.