R-stablo

Izvor: Wikipedija
Skoči na: orijentacija, traži
Jednostavan primjer R-stabla za 2D kvadrate

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[uredi VE | uredi]

Algoritam[uredi VE | uredi]

Pretraga[uredi VE | uredi]

Ulaz je kvadrat pretrage (Query box). Pretraga je slična pretragi u B-stablu, a počinje iz korjenog č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[uredi VE | uredi]

Za umetanje objekta, stablo se prelazi rekurzivno od korjenog č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[uredi VE | uredi]

  • 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[uredi VE | uredi]

Izvori[uredi VE | uredi]

  1. Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: The Priority RTree: A Practically Efficient and WorstCase Optimal RTree
  2. Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing

Vanjske poveznice[uredi VE | uredi]