Abstract
Hierarchical navigable small world (HNSW) graphs get more and more popular onlarge-scale nearest neighbor search tasks since the source codes were releasedtwo years ago. The attractiveness of this approach lies in its superiorperformance over most of the nearest neighbor search approaches as well as itsgenericness to various distance measures. In this paper, several comparativestudies have been conducted on this search approach. The role of hierarchicalstructure in HNSW and the function of HNSW graph itself are investigated. Wefind that the hierarchical structure in HNSW could not achieve "a much betterlogarithmic complexity scaling" as it was claimed in the paper, particularly onhigh dimensional data. Moreover, we find that similar high search speedefficiency as HNSW could be achieved with the support of flat k-NN graph aftergraph diversification. Finally, we point out the difficulty, faced by most ofthe graph based search approaches, is directly linked to "curse ofdimensionality". HNSW, like other graph based approaches, is unable to addresssuch difficulty.