A fast post-processing method for approximate nearest neighbor search uses a precomputed cutoff table to greedily prune candidates and guarantee a minimum pairwise distance among the returned results.
Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We present a theoretical and empirical analysis of the adaptive entry point selection for graph-based approximate nearest neighbor search (ANNS). We introduce novel concepts: $b\textit{-monotonic path}$ and $B\textit{-MSNET}$, which better capture an actual graph in practical algorithms than existing concepts like MSNET. We prove that adaptive entry point selection offers better performance upper bound than the fixed central entry point under more general conditions than previous work. Empirically, we validate the method's effectiveness in accuracy, speed, and memory usage across various datasets, especially in challenging scenarios with out-of-distribution data and hard instances. Our comprehensive study provides deeper insights into optimizing entry points for graph-based ANNS for real-world high-dimensional data applications.
citation-role summary
citation-polarity summary
fields
cs.CV 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table
A fast post-processing method for approximate nearest neighbor search uses a precomputed cutoff table to greedily prune candidates and guarantee a minimum pairwise distance among the returned results.