Térinformatikai adatszerkezetek

Algoritmusok tervezése és elemzése

Frank Krisztina (WUPN2J)

Térinformatikai adatszerkezetek

1. Pont Egy többdimenziós pont reprezentálható sokféle módon. A választott reprezentáció függ attól, hogy milyen alkalmazás során akarjuk használni, és milyen típusú műveleteket akarunk végrehajtani az adatokon. További kérdések is felmerülnek még, úgy mint, az adatbázisunk dinamikus vagy statikus, vagy az hogy mekkora adathalmazzal is kell majd dolgozni.

1.1 Nem-hierarchikus struktúrák: [1] Legegyszerűbb módja pontok tárolásának egy szekvenciális lista. Adott N rekord és k attribútum, viszont ebben az esetben minden keresés O(N*k) műveletigényű, hiszen minden rekordot meg kell vizsgálni. Egy kicsit hatékonyabb megoldás az invertált lista, amelynek a lényege, hogy van két listánk, az egyikben az adatok az x koordináta szerint, a másikban pedig az y koordináta szerint rendezettek. (A listában mutatókat tárolunk.) Ebben az esetben a művelet igény átlagosan O(N I-1/k). Egy másik módszer a fix grid. Ebben az esetben a tér fel van osztva egyenlő méretű cellákra (2dimenziós esetben négyzetekre, 3-dimenziós esetben kockákra)



Az ábrán látható példán a grid egy 100x100as koordináta teret reprezentál, amelyben minden négyzet 20x20as, így összes a tér 25 egyenlő cellára van osztva. Fix grid esetén a keresés átlagos műveletigénye: O(F*2k), ahol F a talált rekordok száma.

1.2. Hierarchikus struktúrák: Hierarchikus adatstruktúrák fontos reprezentációs eszközök sokféle területen, úgy mint képfeldolgozás, grafika, robotika és GIS. Ezek az adatszerkezetek a rekurzív dekompozíció elvén alapulnak, ami hasonló az „oszd meg és uralkodj” elvhez. 1.2.1. Pont negyedelőfa A pont negyedelőfa egyfajta kombinációja a gridnek és a bináris keresőfának, ami egy fa struktúrát eredményez nem egységes méretű cellákkal. Implementáció szempontjából a bináris keresőfa többdimenziós általánosítása. Minden pont egy csúcson helyezkedik el, és minden csúcs egy rekordtípus, ami hét mezőt tartalmaz. (Ebből az első négy a négy gyerekre mutató pointer.)

Műveletek: Beszúrás: A beszúrás hasonlóan működik, mint bináris keresőfák esetében. Lényegében megkeressük a megfelelő rekordot az x és y koordináta alapján, minden csúcsnál kiválasztjuk a megfelelő részfát, és így haladunk tovább, amíg el nem érünk a fa aljára (NIL pointer), ami azt jelenti h megtaláltuk a helyet, ahova be kell szúrni az elemet. Így a beszúrásnak az átlagos műveletigénye O(log4N).



Törlés A törlés már meglehetősen bonyolultabb, mint az előzőekben látottak. Minden csúcsot, aminek a törölt csúcs a gyökere át kell helyezni a fában, ami nagyon drága. A példa bináris keresőfa esetében, ha töröljük az A csúcsot, akkor helyére a D vagy a G kerül, amik láthatóan a legközelebbi értékűek az eredeti – törölt csúcshoz képest. A probléma, hogy ezt nem ilyen könnyű megállapítani a negyedelőfa esetében, hiszen nincs olyan csúcs aminek szimultán az x és az y koordintája is a legközelebb esik a törölt csúcséhoz. Ilyen szempontból nem számít melyik csúcsot helyezzük át, mert úgyis sok más csúcs lesz, amit máshova kell áthelyezni. A pont-negyedelőfában négy jelölt van, mint lehetséges „csere” csúcs – minden negyedhez egy (FIND_CANDIDATE()). Ezek után, ha megvan a jelöltek, ki kell választani a legjobbat bizonyos kritériumok alapján (pl: a határolótengelyhez közelebb eső).

1.2.2. K-d fa (k-dimenziós fa) Tulajdonképpen ez egy bináris keresőfa, ahol minden csúcs egy k-dimenziós pont, azzal a különbséggel, hogy minden mélységi szinten különböző attribútum (vagy kulcs) értéket vizsgálunk. Például 2-dimenziós esetben (2-d fa) a csúcsok x koordinátáit hasonlítjuk össze a gyökérben, illetve a páros mélységi szinteken, a páratlan szinteken pedig az y koordinátát. Tehát a k-d fa előnye a pont-negyedelőfával szemben, hogy egy k-dimenziós tér esetén a k-d fában minden csúcsnál csak egy kulcsértékek kell összehasonlítani, míg a pont-negyedelőfnál az összes kt. Ezzel szemben a pont-negyedlőfának még mindig van egy előnye, mégpedig, hogy eredendően párhuzamos szerkezetű, tehát a k kulcs összehasonlítása végrehajtódhat párhuzamosan. Példa:



1.2.3. Régió negyedelőfa [2] A régió negyedelőfa a tér egy részét reprezentálja 2-dimenzióban. A régiót dekomponálja azáltal, hogy négy negyedbe bontja, majd ezt újra és újra. A végén minden csúcsnak vagy négy gyereke van, vagy pedig nulla, ez esetben a csúcs egy levél. Egy n mélységű régió negyedelőfa például jól használható egy 2n×2n pixel nagyságú kép esetén, ahol minden pixel értéke 0 vagy 1. A gyökér csúcs reprezentálja a teljes kép régiót. Ha a pixelek egy régióban nem egyöntetűen 0-k vagy 1-k, akkor azt a régiót tovább kell negyedelni, egészen addig amíg minden régió vagy csak 0 vagy csak 1 értékű pixeleket tartalmaz.

1.2.4. PR negyedelőfa (Point – Region quadtree) [3] A PR negyedelőfaa a régió negyedelőfa egy adaptációja pont adatokra. A PR negyedelőfa alapvetően úgy épül fel, mint a a szimpla régió negyedelőfa, azzal a különbséggel, hogy a levél csúcsok vagy üresek, vagy tartalmaznak egy adatpontot, és annak koordinátájit. Egy negyed maximum egy adatpontot tartalmazhat. Adatpontok beillesztése a PR negyedelőfába hasonlóképp működik, mint a pont negyedelőfába való beillesztés. Keresésnél, ha egy olyan negyedet találtunk ami már „foglalt” egy másik pont által, akkor negyedelni kell azt a negyedet, egészen addig, amíg a csúcsot egy olyan negyedbe tudjuk beszúrni, ami nem tartalmaz más csúcsot. Ez elég próblémás tud lenni abban az esetben, ha a csúcsok közti euklideszi távolság kicsi, mert akkor nagyon sok negyedelésre van szükség hogy külön régiókba kerüljenek.



2. Index struktúrák Az index egy olyan speciális adatszerkezet, amelyben gyorsan meg tudunk találni egy K1 kulcsértéket (ami akár többször is előfordulhat), majd a kulcsértékről mutatók segítségével gyorsan el tudunk jutni azokhoz a táblabeli sorokhoz, amelyek ezzel a kulcsértékkel rendelkeznek. Ugyanez az ötlet a térbeli indexeknél is. Tehát szükség van egy adatstruktúrára, amiben gyorsan lehet keresni, és a térbeli adatokat is jól jellemez. (Pl. lefedő téglalapokkal)

2.1. R-fa index [4][5] Az R-fa alapötlete, hogy csoportosítsuk az egymáshoz közeli alakzatokat, majd egy magasabb szinten reprezentáljuk azt a minimális lefedő téglalapjával. Így, hogy minden objektum egy határon belül van, a lekérdezések is gyorsabbak lehetnek, hiszen ha egy lekérdezés nem esik bele ebbe határolt régióba, akkor értelemszerűen egyik ezen belül lévő alakzatra sem lesz jó, így már az elején eldönthető. Példa: Keressük azokat az alakzatokat, amik tartalmazzák az adott pontot. Ha nem használnánk indexet, akkor minden alakzaton végig kéne menni, viszont az R-fa index megkönnyíti a dolgunk. Megnézzük először a gyökérelemet, mert ha már az se tartalmazza a pontot, akkor egyik gyereke se. Ha azt kapjuk, hogy tartalmazza, akkor megvizsgáljuk a gyerekeit, hogy melyik lefedő télglalapjába esik bele a pont és arra haladunk tovább lefelé. Ezután két eset lehetséges 1) Egyszercsak olyan szintre érünk, ahol semelyik gyerek se tartalmazza a pontot, holott a szülő csúcs lefedő téglalapja tartalmazta. Ez esetben a pontot egyik alakzat sem tartalmazza. 2) Eljutunk a levél szintig, és megtaláljuk a megfelelő alakzatot/alakzatokat.



Látható, hogy keresésnél az R-fa indexelés nagyon gyors és praktikus, de van hátránya is. Ez például akkor ütközik ki nagyon, amikor olyan alakzattal van dolgunk, ami elég szabálytalan és előnytelen alakú, tehát a lefogó téglalappal se lehet megfelelően közelíteni. Szintén problémát jelent, hogy nehéz vele alkalmazkodni a dinamikus változásokhoz. Tehát ha az adatbázisban az alakzatok változnak, akkor ezzel együtt változik a lefedő téglalap is, és ennek hatása végiggyűrűzik felfele a fán, ami így eléggé költséges.

2.2. Negyedelőfa index [4] Tehát, mint korábban láthattuk, a régió negyedlőfa úgy működött, hogy az alazatunkat negyedüljük újra és újra. Az eljárás során kapott téglalapokat rasztereknek nevezzük. A negyedeléstől függően az eljárás végén lehetnek egységes nagyságú rasztereink, illetve különbözőek is. (Ez alapján nevezzük az indexelést fix indexelésnek, illetve hibrid indexelésnek.) Az alakzatok indexelése azt fogja jelenteni, hogy hozzájuk rendeljük azokat a rasztereket, amelyek nem diszjunktak tőlük. Így az alakzat indexbeli raszterei lefedik az alakzatot. A negyedlőfa indexelés nagy előnye az R-fa indexeléshez képest, hogy sokkal jobban lehet vele közelíteni az alakzatok. Míg az R-fa esetében eléggé rossz közelítést kaptunk a lefedő téglalappal, ha az alakzat túl szabálytalan alakú volt, így ez a negyedelőfa indexeléssel nem baj, mert a hibrid indexelés lehetővé teszi, hogy egészen finom részeket is jól lehessen közelíteni, míg a nagy homogén régiókat nem aprózzuk el. Szintén az előnyére írható, hogy a változásokat is jobban tolerálja. Nem kell a teljes indexstruktúrát újraszervezni, ha valami apró változást történt, hanem csak néhány rasztert hozzáadni, illetve elvenni. Viszont hátránya, hogy tárolásnál jóval nagyobb helyet igényel, mint az R-fa index.



Irodalomjegyzék:

[1]

The Design and Analysis of Spatial Data Structures Hanan Samet - 1989

[2]

The region quadtree http://en.wikipedia.org/wiki/Quadtree#The_region_quadtree

[3]

Hierarchical Spatial Data Structures Hanan Samet

[4]

Térbeli indexelés Nikovits Tibor http://people.inf.elte.hu/nikovits/TERINFO/SDO9_index.doc

[5]

R-tree http://en.wikipedia.org/wiki/R-tree

Térinformatikai adatszerkezetek

Recommend Documents