search

nmslib / hnswlib

Header-only C++/python library for fast approximate nearest neighbors
https://github.com/nmslib/hnswlib
Apache License 2.0
4.12k stars 609 forks source link

hnsw index space complexity #445

Closed jianshu93 closed 1 year ago

jianshu93 commented 1 year ago

Hello Team,

What is the theoretical space complexity of hnsw index with respect to the number of data point (N), I cannot find it out in the paper, I feel like it is some how linear related to N or something.

Thanks,

Jianshu

yurymalkov commented 1 year ago

Hi @jianshu93 The theoretical expected complexity is O(N) in the limit of large N (assuming some stuff like that the graph is similar to true Delaunay graph), similar to skiplist.

jianshu93 commented 1 year ago

Hello @yurymalkov ,

Thanks for the response, I read that in another paper (https://dl.acm.org/doi/abs/10.14778/3489496.3489506?casa_token=1qCegb6AsSgAAAAA:bvML9hjPlwZ8aUxEUHxsgrLSRU-iQ1WjZ8ht8A31tifz8Oa4oEZ6-wowAoroaX2Kw5becyR8EQYz), it was , where and d is the dimension.

yurymalkov commented 1 year ago

Ok. I am not sure about this formula actually, but the N part is correct.