HNSW (Hierarchical Navigable Small World, česky Hierarchický navigovatelný malý svět) je v současnosti jeden z nejpopulárnějších a nejvýkonnějších algoritmů pro přibližné hledání nejbližšího souseda (ANN – Approximate Nearest Neighbor). Ve světě umělé inteligence, strojového učení a vektorových databází slouží jako průmyslový standard pro bleskové vyhledávání podobností v obrovských vícerozměrných datasetech.

Zatímco přesné hledání (k-Nearest Neighbors) vyžaduje porovnání dotazovaného vektoru s každým jednotlivým záznamem v databázi (což je u milionů vektorů extrémně pomalé), HNSW využívá chytrou grafovou strukturu k dosažení sub-milisekundové odezvy při zachování přesnosti často přesahující 99 %.

HNSW kombinuje dva velmi odlišné koncepty z teorie grafů a datových struktur: Navigovatelné sítě malého světa (NSW) a Hierarchii (podobnou Skip Listům).

Teorie „malého světa“ (Small World) vychází ze známého fenoménu šesti stupňů odloučení (každého člověka na planetě lze propojit s kýmkoliv jiným přes maximálně šest známých). V kontextu vektorů to znamená, že body v grafu jsou propojeny primárně se svými nejbližšími sousedy, ale existují zde i záměrná dlouhá spojení (long-range links), která propojují vzdálené shluky dat.

Když v takovém grafu (NSW) hledáte, začnete v náhodném bodě a postupujete přes hrany k bodům, které jsou blíž vašemu cíli. Dlouhá spojení umožňují rychle „přeskočit“ na správnou stranu grafu a krátká spojení pak zajistí jemné dohledání cíle.

Samotný NSW má ale problém: jak graf roste, hledání se může zacyklit nebo zpomalit kvůli příliš mnoha hranám (tzv. „hub nodes“ neboli dálniční uzly, které jsou zahlceny dotazy).

Yu. A. Malkov (autor HNSW) tento problém vyřešil přidáním hierarchie. Inspiroval se pravděpodobnostní datovou strukturou zvanou Skip List (seznam s přeskoky). Zkonstruoval graf do několika vrstev (layers).

HNSW rozděluje vektory do poschodí:

• Vrstvy vyšší úrovně (L2, L3…): Obsahují jen velmi málo vektorů. Slouží jako rychlé dálnice pro obrovské skoky napříč celým datovým prostorem.
• Střední vrstvy (L1): Obsahují více vektorů a slouží k navigaci na úrovni „okresních silnic“.
• Nultá vrstva (L0): Zcela spodní vrstva. Obsahuje všechny vektory v databázi a jejich hustá lokální propojení.

Rozhodnutí, do jaké vrstvy se nový vektor při vkládání dostane, se určuje náhodně pomocí klesající pravděpodobnosti (exponenciálního rozdělení). Většina bodů skončí pouze v nulté vrstvě, hrstka vyvolených „vystoupá“ až do nejvyšších vrstev.

Hledání v HNSW (tzv. Greedy Routing) připomíná přibližování na mapě:

1. Vstupní bod (Entry Point): Algoritmus začne v nejvyšší dostupné vrstvě u předem určeného vstupního uzlu.
2. Hledání v aktuální vrstvě: Prohledá sousedy tohoto uzlu. Pokud najde souseda, který je blíž dotazovanému vektoru, přesune se na něj (hladové hledání / greedy search).
3. Propad do nižší vrstvy: Pokud v aktuální vrstvě už neexistuje žádný uzel, který by byl k cíli blíž (našlo se lokální minimum pro tuto vrstvu), algoritmus „propadne“ do stejného uzlu v o vrstvu nižším patře.
4. Opakování až do L0: Tento proces se opakuje, dokud algoritmus nedosáhne vrstvy 0. Zde provede finální detailní dohledání požadovaného počtu (k) nejbližších sousedů.

Vývojáři používající HNSW (např. v databázích jako je Milvus) mají k dispozici tři klíčové parametry, kterými balancují mezi rychlostí, přesností a spotřebou paměti:

• Extrémní rychlost (Nízká latence): Díky hierarchii odpadá výpočet mnoha zbytečných vzdáleností. Dotazy trvají zlomky milisekund.
• Vysoký Recall: Schopnost najít skutečně nejbližší sousedy s přesností blížící se 100 %.
• Podpora pro aktualizace: Na rozdíl od starších algoritmů (jako jsou stromy kd-trees) HNSW celkem dobře zvládá průběžné přidávání nových dat (streaming).

Největší slabinou HNSW je spotřeba operační paměti (RAM). Struktura grafu, zejména uložení všech hran v paměti a samotných nepředzpracovaných vektorů, vyžaduje, aby celý index sídlil v RAM. Pokud máte 1 miliardu vektorů (např. o 768 dimenzích), samotná data zaberou zhruba 3 TB a grafová struktura HNSW si vyžádá další obrovskou porci paměti.

To dělá HNSW velmi drahým na provoz v obrovských měřítkách (tzv. hyperscale). Pro řešení tohoto problému vznikly alternativy optimalizované pro SSD disky, jako je například algoritmus DiskANN.

• Milvus (vektorová databáze)
• DiskANN (alternativa optimalizovaná na disk)
• Vyhledávání nejbližšího souseda (Wikipedia)
• Malkov, Yu. A., & Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. (Původní vědecká publikace)