k Approximate Nearest Neighbors Search (Nearest Neighbor Search)
Jump to navigation
Jump to search
Description
Within a dataset of $n$ points, find approximately the $k$ closest points to a specified point.
Related Problems
Generalizations: k Nearest Neighbors Search
Parameters
n: number of points in dataset
k: number of neighbors to find
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Hierarchical Navigable Small World (HNSW) | 2018 | $O(nlogn)$ | $O(M)$ | ? experimental results | Deterministic | Time & Space |
| Locality-sensitive hashing | 2010 | $O(nLkt)$ (pre-processing)
$O(L(kt+dnP_2^k))$ (query-time) || $O(nL)$ || c || Deterministic || Time & Space | ||||
| Projected radial search | 2013 | $O(k)$ | $O({1})$ | ? | Deterministic | Time |
| Compression/Clustering (Vector Quantization) | 1992 | Varies by codebook structure | Varies by codebook structure | Deterministic |