Graph-Based Nearest-Neighbor Search without the Spread
$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Approximate k-NN Graph Construction: a Generic Online Approach
Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues arise from many disciplines such as multimedia information retrieval, data-mining and machine learning. They become more and mo…
graph constructionInformation RetrievalRetrievalLabel Noise Robustness for Domain-Agnostic Fair Corrections via Nearest Neighbors Label Spreading
Last-layer retraining methods have emerged as an efficient framework for correcting existing base models. Within this framework, several methods have been proposed to deal with correcting models for subgroup fairness wit…
FairnessFast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph
Approximate nearest neighbor search (ANNS) is a fundamental problem in databases and data mining. A scalable ANNS algorithm should be both memory-efficient and fast. Some early graph-based approaches have shown attractiv…
EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph
Approximate nearest neighbor (ANN) search is a fundamental problem in many areas of data mining, machine learning and computer vision. The performance of traditional hierarchical structure (tree) based methods decreases …
graph constructionCAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs
Approximate Nearest Neighbor Search (ANNS) plays a critical role in various disciplines spanning data mining and artificial intelligence, from information retrieval and computer vision to natural language processing and …
CPUGPUgraph constructionInformation Retrieval+1