k Approximate Nearest Neighbors Search

Within a dataset of nn points, find approximately the kk closest points to a specified point.

Parameters

  • nn: number of points in dataset
  • kk: number of neighbors to find

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms

See more
Hierarchical Navigable Small World (HNSW)2018O(nlog⁡n)O(n \log n)O(M)O(M)
Locality-sensitive hashing2010O(nLkt)O(nLkt) [pre-processing] O(L(kt+dnP2k))O(L(kt+dnP_2^k)) [query-time]O(nL)O(nL)
Compression/Clustering [Vector Quantization]1992Varies by codebook structureVaries by codebook structure

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table