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".

Jednostavan primjer R-stabla za 2D kvadrate

Strukturu podataka dijeli hijerarhijski prostorno ugnježđen, s 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.

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 k odgovarajućem čvoru nasljedniku i svaki lisni čvor sadrži kvadrate prostornih objekata (gdje može biti i pokazivač k nekom prostornom objektu). Za svaki kvadrat i čvor, mora biti odlučeno se li se preklapa s 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 s 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)
• 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

• minimalni obuhvatni kvadrat
• prostorni indeks
• GiST

Izvori

• 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  Arhivirana inačica izvorne stranice od 17. travnja 2018. (Wayback Machine)

Vanjske poveznice

• rtreeportal.org
• R-Trees: A Dynamic Index Structure for Spatial Searching
• Implementacije R-stabla: Java applet  Arhivirana inačica izvorne stranice od 1. svibnja 2007. (Wayback Machine), Common Lisp, .NET  Arhivirana inačica izvorne stranice od 8. veljače 2011. (Wayback Machine), Python