Exploring Hierarchical Navigable Small World

Marianne Haugvaldstad and Brage Vik, interns at Vespa, explored the Hierarchical Navigable Small World (HNSW) algorithm for Approximate Nearest Neighbor (ANN) searches in high-dimensional vector databases. HNSW, known for its efficiency in search engines and recommendation systems, organizes data into layered proximity graphs, allowing rapid identification of relevant results without exhaustive computation. The interns developed visualization tools to demonstrate how the algorithm navigates these graphs, addressing challenges such as disconnected nodes and edge density, which can affect search quality. They also explored dimensionality reduction techniques like Principal Component Analysis to potentially enhance search efficiency, and they evaluated filtering strategies within HNSW, noting its performance under different conditions. Their work not only highlighted the algorithm's effectiveness but also revealed a bug in Vespa's implementation, underscoring the importance of detailed graph analysis. Through hands-on experimentation, they gained valuable insights into ANN search methodologies and contributed meaningful innovations to the Vespa platform.