R-stablo
R-stabla su stabla strukture podataka slična B-stablima, korištena za pristup prostornim podacima tj, za indeksiranje višedimenzionih informacija; npr, (X, Y) koordinate prostornih podataka. Uobičajena upotreba R-stabla mogla bi biti: „Pronađi sve muzeje unutar 2 km od moje trenutne lokacije“.
Strukturu podataka djeli hijerarhijski prostorno ugnežđ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 predefinisanog 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 osiguraju 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 da li da pretražuju unutar čvora nasljednika. U tom slučaju, većina čvorova u stablu nisu nikada „dodirnuti“ tokom 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šćeni da razdvoje čvorove kada oni postanu prepuni, rezultujući kvadratnom i linearnom podtipu R-stabla.
R-stabla ne garantuju tradicionalno dobre performanse u kriznim slučajima, ali generalno se dobro snalaze u stvarnim situacijama. Ipak, novi algoritam koji definiše Prioritete u R-stablu je objavnjen 2004. i obećava efikasnost kao trenutno najefikasaniji metod i ima isti optimum u kriznim slučajevima.
Varijante uredi
- 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 uredi
Pretraga uredi
Ulaz je kvadrat pretrage (Query box). Pretraga je slična pretrazi u B-stablu. Počinje iz korjenog čvora stabla. Svaki unutrašnji čvor sadrži skup kvadrata i pokazivača ka odgovarajućem čvoru nasljedniku i svaki lisni čvor sadrži kvadrate prostornih objekata (pokazivač ka nekom prostornom objektu može biti tu). Za svaki kvadrat i čvoru, mora biti odlučeno da li se preklapa sa pretražnim kvadratom ili ne. Ako da, odgovarajući čvor nasljednik mora takođe biti pretražen. Pretraga se vrši 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 rezultujući skup ako leže unutar pretražnog kvadrata.
Umetanje uredi
Za umetanje objekta, stablo se pređe rekurzivno od korjenog čvora. Svi kvadrati u tekućem internom čvoru se ispituju. Ograničenje najmanje pokrivenosti je uposleno za umetanje objekata, tj, kutija koja treba najmanje uvećanje da obuhvati novi objekat je odabrana. U slučaju gdje više od jednog kvadrata ispunjava taj uslov, odabere 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 objekat. 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
- Sort-Tile-Recursive (STR) [2]
- Pakovano hilbertovo stablo - Koristi Hilbertovu vrijednost centra kvadrata da sortira lisne čvorovei sagradi stablo rekurzivno.
- najbliži-X - Kvadrati su sortirani na x-koordinatui i čvorovi su kreirani.
Vidi još uredi
Literatura uredi
- Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data. R-Trees: A Dynamic Index Structure for Spatial Searching. стр. 47—57. ISBN 978-0-89791-128-3.
- Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer. 2005. R-Trees: Theory and Applications. ISBN 978-1-85233-977-7.
- [1] Архивирано на сајту Wayback Machine (17. април 2018) N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger (1990). „The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles”. SIGMOD Conference. 19 (2): 322—331. doi:10.1145/93605.98741.] Архивирано на сајту Wayback Machine (17. април 2018)
Reference uredi
- ^ Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: The Priority RTree: A Practically Efficient and WorstCase Optimal RTree Arhivirano na sajtu Wayback Machine (6. mart 2021), Pristupljeno 24. 4. 2013.
- ^ Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez:. „STR: A Simple and Efficient Algorithm for R-Tree Packing”. CiteSeerX 10.1.1.106.4996
., Pristupljeno 24. 4. 2013.
Spoljašnje veze uredi
- R-Trees: A Dynamic Index Structure for Spatial Searching
- Implementacije R-stabla: Java applet Arhivirano na sajtu Wayback Machine (1. maj 2007), Common Lisp, .NET, Python.