tag

#nearest-neighbor

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

VP Tree Search

VP Tree Search VP tree search (vantage point tree) organizes points in a metric space by selecting a pivot point and partitioning others based on distance from that pivot. It is designed for efficient nearest neighbor search using triangle inequality based pruning. Problem Given a set of points $S$ in a metric space and a query point $q$, find: $$ \arg\min_{p \in S} d(p, q) $$ Structure Each node stores:...
algorithms searching vp-tree nearest-neighbor
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Cover Tree Search

Cover Tree Search Cover tree search is a metric space search structure designed for nearest neighbor queries. It builds a hierarchy of points where each level covers the level below with exponentially shrinking distance bounds. It provides strong theoretical guarantees in spaces with bounded intrinsic dimension. Problem Given a set of points $S$ in a metric space and a query point $q$, find: $$ \arg\min_{p \in S} d(p, q) $$...
algorithms searching cover-tree nearest-neighbor
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Ball Tree Search

Ball Tree Search Ball tree search organizes points into a hierarchy of nested hyperspheres. Each node represents a ball defined by a center point and a radius, covering all points in its subtree. It is commonly used for nearest neighbor search in metric spaces where distance computations are expensive. Problem Given a set of points in a metric space and a query point $q$, find the nearest neighbor: $$ \arg\min_{p...
algorithms searching ball-tree nearest-neighbor