Down with the Hierarchy: The ‘H’ in HNSW Stands for “Hubs”

Blaise Munyampirwa, Vihan Lakshman, Benjamin Coleman · 2024

Read Down with the Hierarchy: The ‘H’ in HNSW Stands for “Hubs” by Blaise Munyampirwa, Vihan Lakshman, Benjamin Coleman (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01940.txt.

Description

Blaise Munyampirwa, Vihan Lakshman, and Benjamin Coleman ask in 2024 whether the layered design of a leading search index is even needed. HNSW, the dominant tool for fast near-neighbor search over vector embeddings, stacks graphs in a hierarchy to home in on matches. The team benchmarked it against a flat single-layer graph across more large data sets than earlier studies.

On high-dimensional data the flat graph matched the layered one in speed and recall while using less memory. The authors argue that hub nodes form a natural highway inside the flat graph, doing the job the layers were meant to do. Tests on real data back the hub highway idea.

Catalog record

CREATORBlaise Munyampirwa, Vihan Lakshman, Benjamin Coleman
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01940

Browse the full library · About the Tower of Babel