k-d strom (zkratka pro k-dimenzionální strom) je datová struktura v informatice, která slouží k organizaci bodů v prostoru o k dimenzích. Jedná se o speciální typ binárního stromu, který rekurzivně rozděluje prostor pomocí hyperrovin.

Historicky byl k-d strom zlatým standardem pro prostorové vyhledávání (například hledání nejbližšího souseda ve 2D nebo 3D prostoru). Ačkoliv je stále mimořádně užitečný v počítačové grafice nebo geografických informačních systémech (GIS), v moderní umělé inteligenci a vektorových databázích naráží na zásadní matematický limit známý jako prokletí dimenzionality.

Princip k-d stromu spočívá v postupném půlení prostoru. Každý uzel ve stromu reprezentuje určitou oblast (tzv. bounding box) a rozděluje ji na dvě menší poloviny.

Stavba stromu probíhá rekurzivně a střídá jednotlivé osy (dimenze):

1. Výběr osy: V prvním kroku (kořen stromu) se prostor rozdělí podle osy X. V další úrovni stromu se dělí podle osy Y, poté podle osy Z (ve 3D prostoru) a tak dále. Po vyčerpání všech k dimenzí se algoritmus vrátí zpět k ose X.
2. Nalezení mediánu: Algoritmus seřadí všechny body podle aktuální osy a vybere bod, který je přesně uprostřed (medián). Tento bod se stane uzlem stromu.
3. Rozdělení: Body s menší hodnotou na dané ose jdou do levé větve (levý podstrom), body s větší hodnotou do pravé větve.
4. Tento proces se opakuje, dokud v každém listu stromu nezbude jen jeden nebo několik málo bodů.

Hledání v k-d stromu zaručuje nalezení absolutně nejpodobnějšího (nejbližšího) bodu, nejedná se tedy o přibližné hledání (ANN) jako u HNSW. Probíhá ve dvou fázích:

1. Cesta dolů (Greedy Search): Algoritmus postupuje od kořene dolů podobně jako v běžném binárním vyhledávacím stromu. Na každém uzlu se rozhodne, zda jít doleva nebo doprava, podle toho, na jaké straně dělící roviny leží hledaný bod. Takto dojde až na dno (k listu) a označí ho jako „zatím nejlepšího souseda“.
2. Zpětný chod (Backtracking): Skutečně nejbližší bod ale může ležet těsně za hranicí v sousední oblasti. Algoritmus se proto vrací stromem nahoru a kontroluje, zda vzdálenost od hledaného bodu k dělící rovině není menší než vzdálenost k „zatím nejlepšímu sousedovi“ (geometricky: zjišťuje, zda hyperkoule opsaná kolem hledaného bodu neprotíná dělící rovinu). Pokud ano, musí prohledat i druhou větev stromu.

Zatímco pro malý počet dimenzí (typicky do k = 10 až 20) je k-d strom extrémně efektivní a dokáže najít souseda v čase O(log N), u dat s vysokou dimenzionalitou se jeho výkon hroutí.

Moderní AI modely (např. v databázích Milvus nebo Weaviate) používají vektory (embeddings) s dimenzionalitou 384, 768, nebo dokonce 1536 (OpenAI). V takovém vícerozměrném prostoru nastává bizarní geometrický paradox:

• Vzdálenosti mezi body se stávají velmi podobnými.
• Téměř celý objem prostoru se nachází „blízko u stěn“ (okrajů hyperrovin).

Při backtrackingu (zpětném chodu) proto algoritmus k-d stromu zjistí, že jeho testovací hyperkoule protíná téměř všechny dělící roviny. Místo chytrého přeskakování větví tak nakonec musí prohledat téměř celý strom uzel po uzlu. Výkon k-d stromu tak u AI vektorů klesá na úroveň O(N), což je stejné, jako byste databázi prohledávali sekvenčně položku po položce (brute-force).

• HNSW (Hierarchical Navigable Small World) – Moderní náhrada pro vysoké dimenze
• Milvus (vektorová databáze)
• Weaviate (vektorová databáze)
• Článek k-d tree na anglické Wikipedii