A Comparative Study on Hierarchical Navigable Small World Graphs

By Peng-Cheng Lin et al

Published on June 10, 2019

Read the original document by opening this link in a new tab.

Table of Contents

1. Abstract 2. Introduction 3. Review on HNSW Graphs 4. Overview of Comparative Study 5. Experiments

Summary

This paper presents a comparative study on hierarchical navigable small world (HNSW) graphs for large-scale nearest neighbor search tasks. The study investigates the role of hierarchical structure in HNSW and compares its performance with flat k-NN graphs. It is found that the hierarchical structure in HNSW may not achieve significantly better complexity scaling, especially in high-dimensional data. The study also shows that similar search efficiency as HNSW can be achieved with flat graphs after graph diversification. Additionally, it points out the challenges faced by graph-based approaches like HNSW in addressing the 'curse of dimensionality'. Experimental results on various datasets reveal the diminishing advantage of HNSW over flat graph search as data dimensionality increases.