K Approximate Nearest Neighbors Search: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 16: | Line 16: | ||
== Table of Algorithms == | == Table of Algorithms == | ||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | |||
|- | |||
| [[Hierarchical Navigable Small World (HNSW) (k Approximate Nearest Neighbors Search (k-ANNS) Nearest Neighbor Search)|Hierarchical Navigable Small World (HNSW)]] || 2018 || $O(nlogn)$ || $O(M)$ || ? experimental results || Deterministic || [https://doi.org/10.1109/TPAMI.2018.2889473 Time] & [https://arxiv.org/abs/1603.09320, Space] | |||
|- | |||
| [[Locality-sensitive hashing (k Approximate Nearest Neighbors Search (k-ANNS) Nearest Neighbor Search)|Locality-sensitive hashing]] || 2010 || $O(nLkt)$ (pre-processing) | |||
$O(L(kt+dnP_2^k))$ (query-time) || $O(nL)$ || c || Deterministic || [http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf Time] & [https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search Space] | |||
|- | |||
| [[Projected radial search (k Approximate Nearest Neighbors Search (k-ANNS) for a dense 3D map of geometric points Nearest Neighbor Search)|Projected radial search]] || 2013 || $O(k)$ || $O({1})$ || ? || Deterministic || [http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf Time] | |||
|- | |||
| [[Compression/Clustering (Vector Quantization) (k Approximate Nearest Neighbors Search (k-ANNS) Nearest Neighbor Search)|Compression/Clustering (Vector Quantization)]] || 1992 || Varies by codebook structure || Varies by codebook structure || || Deterministic || | |||
|- | |||
|} | |||
Revision as of 13:04, 15 February 2023
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 |