Locality-sensitive hashing (k-ANNS Nearest Neighbor Search)
Jump to navigation
Jump to search
Time Complexity
$O(nLkt)$ (pre-processing) $O(L(kt+dnP_2^k))$ (query-time)
Space Complexity
$O(nL)$ hash table cells
(https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search)
Description
Approximate?
Approximate
Approximation Factor: c
Randomized?
No, deterministic
Model of Computation
Year
2010