k-d tree

k-d tree (tsz. k-d trees)

1. (informatika) A k-d tree (vagy k-dimensional tree, azaz k-dimenziós fa) egy térbeli adatstruktúra, amelyet többdimenziós adatok hatékony keresésére használnak. Gyakori alkalmazási területei közé tartozik a gépi tanulás, adatbázisok, számítógépes grafika, valamint a közeli szomszéd keresés (k-NN) algoritmusok. A következő leírásban 1000 szóban részletezzük, hogyan működik, milyen célokra használható, és mik a főbb jellemzői.

A k-d tree egy bináris keresőfa, amelyet k dimenziós pontok (pl. (x, y) vagy (x, y, z, w, ...)) tárolására és hatékony lekérdezésére terveztek. Minden egyes szinten a fa egy adott dimenzát használ a pontok szétválasztására (pl. először x, majd y, majd z, és így tovább körforgásban).

Példa: Ha 2D pontokat (x, y) tárolunk, a fa első szintjén x szerint, a másodikon y szerint hasonlítunk, a harmadikon ismét x, stb.

A faépítés során:

1. Válasszuk ki a tengelyt a mélység (depth) alapján: axis = depth % k.
2. A pontokat az adott tengely szerint rendezzük.
3. Válasszuk ki a mediánt – ez lesz az aktuális csomópont.
4. Az alatta és felette lévő pontok a bal és jobb részfákba kerülnek.
5. Rekurzívan ismételjük a lépéseket a részfákon.

Példa (2D):

Pontok: (7,2), (5,4), (9,6), (2,3), (4,7), (8,1)

Első tengely: x → sorbarendezve x szerint → medián = (7,2) → gyökér. Bal oldalra megy (2,3), (4,7), (5,4), jobb oldalra (8,1), (9,6). Következő szint tengelye: y. Rekurzívan folytatjuk.

Ha egy ponthoz legközelebbi másik pontot keresünk, a k-d fa hatékony keresést biztosít:

• Mélyre lemegyünk, követve a tengelyeken a megfelelő oldalt.
• Visszafelé jövet minden szinten megnézzük, hogy van-e értelme a másik ágat is vizsgálni (ha a gömbmetszet belelóg a másik részfába).
• A lekérdezés időkomplexitása ideális esetben O(log n), de legrosszabb esetben akár O(n) is lehet.

Pl. keresés x ∈ és y ∈ intervallumokban. Rekurzívan bejárjuk a fát, és csak akkor nézünk be egy részfába, ha az adott tartományba eshet.

A legrosszabb esetek elkerüléséhez fontos a kiegyensúlyozott fa létrehozása (pl. újraépítés időnként).

Minden csomópont (node) tartalmaz:

• Egy k dimenziós pontot (pl. std::vector<double>),
• Bal és jobb gyermekmutatót (left, right),
• Tengelyt, amely szerint szétválasztottuk.

Példa C++ szerű szerkezet:

struct KDNode {
    std::vector<double> point;
    int axis;
    KDNode* left;
    KDNode* right;
};

1. Gépi tanulás
   • k-NN osztályozás
   • Dimenziós csökkentés (pl. PCA utáni keresés)
2. Számítógépes grafika
   • Objektumkövetés, ütközésvizsgálat
3. Robotika
   • Navigációs pontok hatékony kezelése
4. Játékfejlesztés
   • NPC-k közti távolságalapú döntések
5. GIS és térinformatika
   • Helyalapú lekérdezések (pl. „keresd meg a legközelebbi benzinkutat”)

• Curse of dimensionality: ha a dimenziók száma nagy (k >> 10), a keresési teljesítmény gyorsan romlik.
• Egyenlőtlen adateloszlás: torz fához vezethet, ezért érdemes újraépíteni vagy kiegyensúlyozó algoritmusokat alkalmazni.

• Ball tree
• VP-tree
• Approximate Nearest Neighbor (ANN) módszerek, pl. FAISS, HNSW

A k-d tree egy hatékony, keresés-orientált adatstruktúra, amely többdimenziós pontokat kezel és keres bennük. Előnye, hogy:

• jól működik kis és közepes dimenziók esetén,
• gyors lekérdezést biztosít,
• egyszerűen implementálható.

Viszont nagy dimenzióknál már nem a legjobb választás, ott más módszerek kerülnek előtérbe.

• k-d tree - Szótár.net (en-hu)
• k-d tree - Sztaki (en-hu)
• k-d tree - Merriam–Webster
• k-d tree - Cambridge
• k-d tree - WordNet
• k-d tree - Яндекс (en-ru)
• k-d tree - Google (en-hu)
• k-d tree - Wikidata
• k-d tree - Wikipédia (angol)