K Approximate Nearest Neighbors Search: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 7: Line 7:


Generalizations: [[k Nearest Neighbors Search]]
Generalizations: [[k Nearest Neighbors Search]]
Subproblem: [[k-ANNS for a dense 3D map of geometric points]]


== Parameters ==  
== Parameters ==  


n: number of points in dataset
$n$: number of points in dataset


k: number of neighbors to find
$k$: number of neighbors to find


== Table of Algorithms ==  
== Table of Algorithms ==  


{| class="wikitable sortable"  style="text-align:center;" width="100%"
Currently no algorithms in our database for the given problem.
 
! 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 || 
|-
|}

Latest revision as of 08:52, 10 April 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

Subproblem: k-ANNS for a dense 3D map of geometric points

Parameters

$n$: number of points in dataset

$k$: number of neighbors to find

Table of Algorithms

Currently no algorithms in our database for the given problem.

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=K_Approximate_Nearest_Neighbors_Search&oldid=46846"