R*-fa

Az R*-fák a térinformációk indexelésére használt R-fák egy változata . Az R*-fák létrehozása valamivel magasabb költséggel jár, mint a szabványos R-fáké, mivel előfordulhat, hogy az adatokat újra kell rendezni (törlés + beszúrás), de az eredményül kapott fa általában jobb lekérdezési teljesítményt nyújt. A szabványos R-fához hasonlóan pontokat és térbeli adatokat is tárolhat. A fát Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider és Bernhard Seeger javasolta 1990-ben [1] .

Az R*-fák és az R-fák közötti különbség

A lefedettség és az átfedés minimalizálása fontos az R-fák teljesítménye szempontjából. Az átfedés azt jelenti, hogy adatlekérdezéskor vagy beszúráskor a fa egynél több ágát ki kell bontani (az adatok átfedhető területekre való felosztása miatt). A minimális lefedettség javítja a törlést azáltal, hogy lehetővé teszi a teljes oldalak gyakrabban történő kizárását a keresésekből, különösen a negatív tartományú lekérdezések esetében. Az R*-fa mindkét értéket megpróbálja csökkenteni a beolvasott csomópontfelosztó algoritmus és a csomóponttúlcsordulás esetén kényszerített újratelepítés koncepciójának kombinációjával. A megközelítés azon a megfigyelésen alapul, hogy az R-fa struktúrák nagyon érzékenyek a faelemek beillesztési sorrendjére, így a beillesztésen alapuló (nem tömeges terhelésű) struktúrák nagyobb valószínűséggel szuboptimálisak. A faelemek törlése és újbóli beillesztése lehetővé teszi számukra, hogy „találjanak” egy olyan helyet a fában, amely alkalmasabb, mint az eredeti helyük.

Amikor egy csomópont túlcsordul, néhány elemét eltávolítják a csomópontból, és újra telepítik a fába. (A művelet során egy másik csomópont túlcsordulása okozta végtelen lépcsőzetes alaphelyzetbe állítás elkerülése érdekében az alaphelyzetbe állítási eljárás csak egyszer hívható meg a fa minden szintjén új elem beszúrásakor.) Ez jobban fürtözött elemcsoportokat eredményez a csomópontok, csökkentve a csomópontok lefedettségét. Ezenkívül gyakran a csomópont felosztása gyakran késik, ami a csomópont átlagos kitöltésének növekedéséhez vezet. Az újrabeillesztés felfogható a növekvő fa optimalizálására szolgáló technikának, amikor egy csomópont túlcsordul.

Teljesítmény

• A továbbfejlesztett particionálási heurisztika téglalap alakú oldalakat eredményez, így számos algoritmushoz jobban megfelel.
• Az újrabeillesztés módszere optimalizálja a meglévő fát, de növeli a bonyolultságot.
• Hatékonyan karbantartja a pontokat és a térbeli adatokat.

• Különféle particionálási megközelítések eredményei a német postahivatalok adatbázisán

• R-fa négyzet alakú Gutman partícióval [2] .
  Sok oldal balról jobbra terjed Németországban, és az oldalak nagyban átfedik egymást. Ez nem túl kedvező tulajdonság a legtöbb alkalmazás számára, amelyekhez gyakran csak kis téglalap alakú, sok csíkkal metsző területekre van szükség.

• R-fa lineáris Anga-Tan partícióval [3] .
  Bár a téglalapok nem olyan hosszúak, mint a Gutmann-féle csempézésnél, a sávozási probléma az oldalon szinte minden lapot érint. A lapoldalak kevéssé fedik egymást, de a kézikönyvoldalak sokat fedik egymást.

• Egy fa R* topológiai partíciója [1] .
  Az oldalak nagyon kevéssé fedik egymást, mivel az R* fa megpróbálja minimalizálni az átfedő oldalakat, az újrabeillesztés pedig tovább optimalizálja a fát. A particionálási stratégia sem részesíti előnyben a sávokat, így az így kapott oldalak alkalmasabbak leképezési alkalmazásokhoz.

Algoritmus és összetettség

• Az R*-fa ugyanazt az algoritmust használja a lekérdezésekhez és törlésekhez, mint a normál R-fa .
• A beszúráshoz az R*-fa kombinált stratégiát használ. A levél csomópontjainál az átfedés minimális, míg a belső csomópontoknál a lineáris méretek és a terület minimalizálva van.
• A particionáláshoz az R*-fa topológiai particionálást használ, amely kiválasztja a tengelyek particionálását a kerület mentén, majd az átfedést minimalizálja.
• A továbbfejlesztett felosztási stratégia mellett az R*-fa igyekszik elkerülni a felosztást, amikor objektumokat és részfákat újra beillesztenek a fába, a kiegyensúlyozott B-fa koncepciójának szellemében .

A legrosszabb eset lekérdezései és az eltávolítás bonyolultsága megegyezik az R-fában lévőkkel. Az R*-fa beillesztési stratégia összetett , és összetettebb, mint az R-fa lineáris felosztási ( ) stratégiája, de kevésbé összetett, mint a négyzetes felosztás ( ) stratégia az objektumok oldalméretére vonatkozóan , és kis mértékben hozzájárul a az általános összetettség. A teljes beillesztési komplexitás hasonló marad az R-fához: az újrabeillesztés legfeljebb a fa egy ágát érinti, és ezért ismételt beillesztéseket ad, ami teljesítményében összemérhető egy normál R-fával. Tehát egy R*-fa általános összetettsége megegyezik egy normál R-fa összetettségével.

A teljes algoritmus megvalósításának számos sarokesetet és függő helyzetet kell kezelnie, amelyekről itt nem lesz szó.

Jegyzetek

1. ↑ 1 2 Beckmann, Kriegel, Schneider, Seeger, 1990 , p. 322.
2. ↑ Guttman, 1984 , p. 47.
3. ↑ Ang, Tan, 1997 , p. 337–349.

Irodalom

• Beckmann N., Kriegel HP, Schneider R., Seeger B. Az R*-fa: hatékony és robusztus hozzáférési módszer pontokhoz és téglalapokhoz // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data - SIGMOD '90 . - 1990. - ISBN 0897913655 . doi : 10.1145 / 93597.98741 .
• Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching // Az 1984-es ACM SIGMOD nemzetközi adatkezelési konferencia előadásai - SIGMOD '84 . - 1984. - ISBN 0897911288 . - doi : 10.1145/602259.602266 .
• Ang CH, Tan TC Új lineáris csomópontfelosztó algoritmus R-fák számára // Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Németország, 1997. július 15–18. / Michel Scholl, Agnès Voisard. - Springer, 1997. - T. 1262. - (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-63238-7_38 .