Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor Search)
Jump to navigation
Jump to search
Time Complexity
$O(nlogn)$
Space Complexity
$O(M)$ bytes of memory
(https://arxiv.org/abs/1603.09320, "Memory usage is proportional to choice of M")
Description
Approximate?
Approximate
Approximation Factor: ? experimental results
Randomized?
No, deterministic
Model of Computation
Year
2018
Reference
https://doi-org.ezproxy.canberra.edu.au/10.1109/TPAMI.2018.2889473