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
| CREATOR | Blaise Munyampirwa, Vihan Lakshman, Benjamin Coleman |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01940