Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Novel ConceptsSimilar Papers 제목 키워드 기반
Recurring Auctions with Costly Entry: Theory and Evidence
Recurring auctions are ubiquitous for selling durable assets like artworks and homes, with follow-up auctions held for unsold items. We investigate such auctions theoretically and empirically. Theoretical analysis demons…
Estimating Export-productivity Cutoff Contours with Profit Data: A Novel Threshold Estimation Approach
This paper develops a novel method to estimate firm-specific market-entry thresholds in international economics, allowing fixed costs to vary across firms alongside productivity. Our framework models market entry as an i…
Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysis
Combining gradient compression methods (e.g., CountSketch, quantization) and adaptive optimizers (e.g., Adam, AMSGrad) is a desirable goal in federated learning (FL), with potential benefits on both fewer communication r…
Deep LearningFederated LearningQuantizationCorpus-Based Research into Verb-Forming Suffixes in English: Its Empirical and Theoretical Consequences
The present study explores the semantic and structural aspects of word formation processes in English, focusing on how verbs are derived by the suffixes -ize, -ify, -en, and -ate. Based on relevant derivatives extracted …
A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization
It is known that adaptive optimization algorithms represent the key pillar behind the rise of the Machine Learning field. In the Optimization literature numerous studies have been devoted to accelerated gradient methods …