QK-d-fák
Dolgozatomban egy új, általános, többdimenziós adatstruktúrát mutatok be és elemzek: a QK-d-fát. Ezen új struktúra általánosítása a különböző területeken – mint például a számítógépes grafika – is alkalmazott K-d-fáknak, illetve a Quad-fáknak (négyfáknak).
A K-d-fák és a Quad-fák olyan adatstruktúrák, melyek k-dimenziós rekordokat tárolnak és segítségükkel asszociatív kereséseket hajthatunk végre. K-d-fák esetén a csomópontoknak kettő gyereke lehet, a jobb gyerekei mindig kisebbek nála, a bal gyerekei mindig nagyobbak nála egy meghatározott dimenzió szerint -- ezt nevezzük az adott dimenzió szerinti diszkriminációnak. Quad-fáknál minden csomópontban minden egyes dimenzió szerint diszkriminálunk, így a csomópontoknak pontosan 2^k gyereke van.
A K-d-fák előnye a Quad-fákkal szemben, hogy kevesebb memóriát igényelnek, míg a Quad-fák a belső úthosszukat (Internal Path Length, IPL) tekintve – mely összefüggésben van a rajtuk elvégzett keresési és frissítési műveletek idejével – jobbak a K-d-fákkal szemben. Ezeket összevetve felmerül a kérdés, hogy vajon létezik-e olyan adatstruktúra, amely mind a memóriát, mind az IPL-t tekintve előnyös.
Erre a kérdésre adnak választ a QK-d-fák, amelyek legfontosabb tulajdonsága, hogy külön-külön megadhatjuk a csomópontokra, hogy mely dimenziók szerint diszkrimináljanak. Ebből következik azonban, hogy a QK-d-fák felépítése nem egyértelmű, csomópontonként és dimenziónként dönteni kell, hogy diszkrimináljunk-e vagy sem. E döntések meghozatalára különböző, általam definiált heurisztikákat használtam.
A K-d-, Quad-, és KQ-d-fákon egy általam készített szoftverrel összehasonlító kísérleteket végeztem. Az eredmények az mutatták, hogy megfelelő paraméterbeállításokkal lehetséges a memóriaterület és az IPL szerinti igényekre szabott QK-d-fákat építeni, illetve általánosabban, hogy ennek az új adatszerkezetnek van létjogosultsága a hagyományos adatstruktúrák mellett.
szerző
-
Bereczky Nikolett
mérnökinformatikus
nappali
konzulensek
-
Dr. Németh Krisztián
adjunktus, Távközlési és Médiainformatikai Tanszék -
Dr. Duch Amalia
munkatárs, Automatizálási és Alkalmazott Informatikai Tanszék
