QK-d-fák

Szerző: 
Bereczky Nikolett
Konzulens (TMIT): 
Konzulens (külső): 
Dr. Duch Amalia (Univ. Politecnica de Catalunya, Dept. LSI)
Év: 
2012
Szekció: 
Modellezés és szimuláció szekció
Helyezés: 
1. helyezés
Különdíj: 
Morgan Stanley Női Egyenjogusági és Együttműködési díj

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.