R-stablo
R-stabla su stabla strukture podataka slična B-stablima, korištena za pristup prostornim podacima tj., za indeksiranje višedimenzijskih informacija; npr., (X, Y) koordinate prostornih podataka. Uobičajena upotreba R-stabla mogla bi biti: "Pronađi sve muzeje unutar 2km od moje trenutne lokacije".
Strukturu podataka dijeli hijerarhijski prostorno ugnježđen, sa mogućim preklapanjem, minimalni obuhvatni kvadrat (MBR, još poznat kao bounding box, tj. "kvadrat (rectangle)", od čega "R" u R-stablu).
Svaki čvor R-stabla ima promjenjiv broj ulaza (do nekog predefiniranog maksimuma). Svakim ulazom unutar ne-lisnog čvora pohranjuju se dva podatka: način identifikacije čvora nasljednika i minimalna obuhvatna kutija svih ulaza unutar čvora nasljednika.
Algoritmi unosa i brisanja obuhvatnih kutija koriste obuhvatne kutije iz čvorova da bi osigurali da su "obližnji" elementi postavljeni u isti lisni čvor (pogotovo, novi element će ići u lisni čvor koji zahtijeva najmanje uvećanje obuhvatne kutije). Svaki ulaz unutar lisnog čvora pohranjuje dva podatka: način identifikacije stvarnog elementa podatka (koji, alternativno, mogu biti postavljeni direktno u čvor), i okvirnu kutiju elementa podatka.
Slično, algoritmi pretrage (naprimjer; presjek, sadržavanje, najbliži) koriste obuhvatne kutije da odrede pretražuju li unutar čvora nasljednika. U tom slučaju, većina čvorova u stablu nisu nikada "dodirnuti" tijekom pretrage. Kao B-stabla, ovo čini R-stabla pogodnim za baze podataka, gdje čvorovi mogu biti pohranjeni u memoriju kad je to potrebno.
Različiti algoritmi mogu biti iskorišteni za razdvojanje čvorova kada oni postanu prepuni, rezultirajući kvadratnom i linearnom podtipu R-stabla.
R-stabla ne jamče tradicionalno dobre performanse u kriznim slučajima, ali generalno se dobro snalaze u stvarnim situacijama. Ipak, novi algoritam koji definira Prioritete u R-stablu je objavnjen 2004. godine i obećava efikasnost kao trenutno najefikasanija metoda i ima isti optimum u kriznim slučajevima.
Varijante
- R* stablo
- R+ stablo
- Hilbertovo R-stablo
- Prioritetno R-stablo (PR-stablo) - PR-stablo ima performanse slične najboljoj poznatoj varijanti R-stabla u stvarnim situacijama i relevantan raspored podataka, ali ih značajno nadmašuje u ekstremnijim slučajevima.[1]
Algoritam
Pretraga
Ulaz je kvadrat pretrage (Query box). Pretraga je slična pretragi u B-stablu, a počinje iz korijenog čvora stabla. Svaki unutrašnji čvor sadrži set kvadrata i pokazivača ka odgovarajućem čvoru nasljedniku i svaki lisni čvor sadrži kvadrate prostornih objekata (gdje može biti i pokazivač ka nekom prostornom objektu). Za svaki kvadrat i čvor, mora biti odlučeno se li se preklapa sa pretražnim kvadratom ili ne. Ako da, odgovarajući čvor nasljednik mora također biti pretražen. Pretraga se radi rekurzivno sve dok svi preklapajući čvorovi ne budu zaobiđeni. Kada je lisni čvor dostignut, sadržane obuhvatne kutije (kvadrati) se testiraju kvadratom pretrage i objekti (ako ih ima) se smještaju u rezultirajući set ako leže unutar pretražnog kvadrata.
Umetanje
Za umetanje objekta, stablo se prelazi rekurzivno od korijenog čvora. Svi kvadrati u tekućem internom čvoru se ispituju. Ograničenje najmanje pokrivenosti je uposleno za umetanje objekata, tj. odabrana je kutija koja treba najmanje uvećanje da obuhvati novi objekt. U slučaju gdje više od jednog kvadrata ispunjava taj uvjet, odabire se onaj sa najmanjom površinom. Umetanje se nastavlja rekurzivno u odabranom čvoru. Jednom kad je dostignut lisni čvor, ako lisni čvor nije pun, neposredno se umeće objekt. Ako je lisni čvor popunjen, on mora biti podijeljen prije umetanja. Nekoliko algoritama za podjelu je predloženo za dobre performanse R-stabla.
Umetanje pakovanja
- Sort-Tile-Recursive (STR)[2]
- Pakirano hilbertovo R-stablo - Koristi Hilbertovu vrijednost središta kvadrata da sortira lisne čvorove i sagradi stablo rekurzivno.
- najbliži-X - Kvadrati su sortirani na x-koordinatui i čvorovi su kreirani.
Poveznice
Izvori
- ↑ Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: The Priority RTree: A Practically Efficient and WorstCase Optimal RTree
- ↑ Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing
- Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57. ISBN 0-89791-128-8
- Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer, 2005. ISBN 1-85233-977-2
- N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331
Vanjske poveznice
- rtreeportal.org
- R-Trees: A Dynamic Index Structure for Spatial Searching
- Implementacije R-stabla: Java applet, Common Lisp, .NET, Python