Part II — From proximity graphs to HNSW

Part II tells the story from flat proximity graphs to hierarchical navigable small worlds: how neighbor graphs search without a tree, where NSW-style designs helped and then stalled, and what hierarchy adds.
Created: Updated: 2 min read

These are the topics in this section, each on its own page with a stable path you can bookmark or share.

What topics are covered in this section?

Part II tells the story from flat proximity graphs to hierarchical navigable small worlds: how neighbor graphs search without a tree, why NSW-style designs helped and then stalled, and what layering adds in HNSW.

Why this Part sits between foundations and algorithms?

Part I motivates ANN; Part II introduces the graph paradigm HNSW belongs to. You will see greedy routing on proximity graphs, small-world shortcuts, hub degree problems, and the hierarchical fix that separates long-range and local links across layers. That narrative makes Part III’s detailed search and build procedures feel inevitable rather than arbitrary.

Three chapters carry the arc from graphs, through NSW limits, to HNSW’s core idea.

How should you read it?

Begin with proximity graphs without hierarchy, then small-world and NSW limitations, then the layered HNSW idea. Graph-theory and NSW glossary entries support each chapter. Resist skipping straight to parameters until this Part clarifies what the hierarchy is for.

Weaviate’s default index is an HNSW descendant of this lineage – Part II is why that design won so much mindshare.

What comes after?

Finish the three chapters, then move to Part III for step-by-step search and insertion. Use the graph-based-alternatives glossary when you want NSW contrasted with NSG or Vamana.

Part II is the conceptual bridge into HNSW. Next, open “How do proximity graphs support nearest-neighbor search without a hierarchy?” and continue through the Part in order.