Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor 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")

Approximate?

Approximate

Approximation Factor: ? experimental results

Randomized?

No, deterministic

Year

2018

Reference

https://doi.org/10.1109/TPAMI.2018.2889473