A Comparative Study on Hierarchical Navigable Small World Graphs
Hierarchical navigable small world (HNSW) graphs get more and more popular on
large-scale nearest neighbor search tasks since the source codes were released
two years ago. The attractiveness of this approach lies in its superior
performance over most of the nearest neighbor search approaches as well as its
genericness to various distance measures. In this paper, several comparative
studies have been conducted on this search approach. The role of hierarchical
structure in HNSW and the function of HNSW graph itself are investigated. We
find that the hierarchical structure in HNSW could not achieve "a much better
logarithmic complexity scaling" as it was claimed in the paper, particularly on
high dimensional data. Moreover, we find that similar high search speed
efficiency as HNSW could be achieved with the support of flat k-NN graph after
graph diversification. Finally, we point out the difficulty, faced by most of
the graph based search approaches, is directly linked to "curse of
dimensionality". HNSW, like other graph based approaches, is unable to address
such difficulty.