Get Started
Home
Topics
Search
Library
Research questionHow does graph-based approximate nearest-neighbor search cost scale with dataset size relative to intrinsic dimensionality at fixed recall?Graph-based vector indexes are often expected to have polylogarithmic search growth, but this claim is not established across practical dataset scales. Search cost may instead follow sublinear power-law growth before transitioning to slower growth once the data resolves its underlying distribution.
AI
Information Retrieval
Research Paper
Technology
Latest papersRecent research connected to this question, newest first.A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector SearchApplies to approximate nearest-neighbor search in graph-based indexes, notably HNSW and Vamana. The evidence covers tested datasets, recall targets, query hardness levels, and index configurations; theoretical results address exact and bounded-degree constructions, while the transition to subpolynomial growth is observed only for datasets large enough relative to their intrinsic dimensionality.research paper · Sep 2, 2026
Related questions
How can image retrieval rankings capture neighborhood context in high-dimensional feature spaces?What are the fundamental sample-size limits for estimating diffusion-based local intrinsic dimension at finite smoothing scales?How can a model select the correct entity-specific parametric memory for graph queries without query-time text or semantic similarity?How can graph neural networks capture long-range interactions without oversmoothing or oversquashing on diverse large graphs?