R* stabla

R*-stabla su varijanta R-stabala koja se koriste za indeksiranje prostornih informacija. R*-stabla imaju neznatno veću cenu konstrukcije od standardnih R*-stabala, zbog mogućnosti ponovnog unosa

podataka;ali dobijeno drvo će uglavnom imati bolje performanse upita. Kao i standardno R-stablo, R*-stablo može skladištiti i pokazivačke i prostorne podatke. Predloženo je od strane Norberta Bekmana, Hans–Pitera Krigela, Ralfa Šnajdera, i Bernarda Sigera 1990. godine.^[1]

Razlike između R*-stabala i R-stabala

Minimizacija i pokrivenosti i preklapanja je krucijalna za performanse R-stabala. Preklapanje znači da u podacima upita ili umetanja, više od jedne grane stabla mora biti proširena (usled toga što se podaci dele u sekcije koje se mogu preklapati). Minimalna pokrivenost unapređuje performanse orezivanja, što dozvoljava isključivanje čitavih stranica iz pretrage češće nego inače, u praksi za upite negativnog dometa.

R*-stablo pokušava da smanji oba, korišćenjem kombinacije prerađenog čvora podeljenog algoritma i koncepta nasilnog ponovnog umetanja u čvor prelivanja. Ovo je bazirano na zapažanju da su strukture R-stabala vrlo osetljive do granice u kojoj se unosi ubacuju, za tako izgrađene strukture sa pojedinačnim unosom, (radije nego strukture sa više unosa odjednom) je veća mogućnost da budu sub-optimalne. Brisanje, i ponovno ubacivanje unosa pomaže im da „nađu“ mesto u stablu koje im više odgovara nego originalna lokacija.

Kada dođe do prelivanja čvora, deo unosa biva uklonjen iz čvora i ponovo ubačen u stablo. (U cilju izbegavanja neodređenih kaskada ponovnog ubacivanja unosa uzrokovanim narednog prelivajućeg čvora, rutina ponovnog umetanja unosa može biti pozvana samo jednom u svakom nivou stabla prilikom unošenja bilo kojeg novog unosa). Ovo ima efekat proizvodnje više dobro-klasterovanih grupa unosa u čvorovima, smanjujući pokrivenost čvora. Štaviše sama deljenja čvora su često odložena, što prouzrokuje rast prosečnog zauzimanja čvora. Ponovno umetanje može se posmatrati kao metod inkrementalne optimizacije stabla, izazvane čvorom prelivanja.

Performanse

Poboljšane izdeljene heuristike proizvode strane koje su više pravougaone, i na taj način bolje za mnoge aplikacije
Metod ponovnog unosa optimizuje postojeće stablo, ali mu povećava i kompleksnost.
Efikasno podržava pokazivačke i prostorne podatke istovremeno.

Efekti različitih heuristika deljenja u bazi sa Nemačkim poštanskim okruzima

R-stablo sa Gutmanovim kvadratnim deljenjem.^[2]
Postoje mnoge strane koje su proširene od istoka do zapada celom Nemačkom, i strane se dosta preklapaju. Ovo nije pogodno za većinu aplikacija, kojima često treba samo mala pravougaona oblast koja se seče sa mnogim pačićima.
R-stablo sa Ang-Tanovim linearnim deljenjem.^[3]
Dok se parčići ne rasprostiru kao i sa Gutmanom, problem presecanja utiče skoro na svaku stranu lista. Strane lista se preklapaju malo, ali strane direktorijuma potpuno.
R*-stablo topološko deljenje.^[1]
Strane se preklapaju jako malo jer R*-stablo pokušava da minimizuje preklapanje strana, i ponovni unosi su još više optimizovali stablo. Strategija deljenja takođe ne preferira parčiće, pa su konačne strane su mnogo više korisnije za obične aplikacije sa mapama.

Algoritam i kompleksnost

R*-stablo koristi isti algoritam za brisanje i upit operacija kao i R-stablo.
Prilikom unosa R*-stablo koristi kombinovanu strategiju. Za čvorove lista, preklapanje je minimizovano, dok za unutrašnje čvorove proširenja i oblast su minimizovani.
Prilikom deljenja, R*-stabla koriste topološko deljenje, koje bira izdeljenu osu baziranu na parametrima, zatim minimizuje preklapanja.
Dodatno poboljšanoj strategiji deljenja, R*-stablo takođe pokušava da izbegne deljenja ponovnim unosom objekata i podstabala u stablo, inspirisano konceptom balansirajućeg B-stabla.

Očigledno, najgori slučaj kompleksnosti upita i brisanja su identična R-stablu. Strategija unosa kod R*-stabala je sa ${\mathcal {O}}(M\log M)$ kompleksnija nego linearna strategija deljenja ( ${\mathcal {O}}(M)$ ) R-stabala, ali manje kompleksna nego kvadratna strategija deljenja ( ${\mathcal {O}}(M^{2})$ ) za stranu veličine od $M$ objekata i ima malo uticaja na ukupnu složenost. Ukupna složenost unosa još uvek može da se poredi sa R-stablima: ponovna ubacivanja utiču najviše na jednu granu stabla i tako ${\mathcal {O}}(\log n)$ ponovnih unosa, u poređenju sa obavljanjem deljenja na regularnom R-stablu. Sve u svemu, složenost R*-stabla je ista kao i kod regularnog R-stabla. Implementacija potpunog algoritma mora rešiti mnoge specijalne slučajeve, i tesne situacije koje ovde nisu diskutovane.

Reference

^ ^a ^b Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). „The R*-tree: an efficient and robust access method for points and rectangles”. Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 (PDF). str. 322. ISBN 0897913655. doi:10.1145/93597.98741.
^ Guttman, Antonin (1984). „R-trees”. Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. str. 47. ISBN 0897911288. S2CID 876601. doi:10.1145/602259.602266.
^ Ang, C. H.; Tan, T. C. (1997). „New linear node splitting algorithm for R-trees”. Advances in Spatial Databases. Lecture Notes in Computer Science. 1262. str. 337—349. ISBN 978-3-540-63238-2. doi:10.1007/3-540-63238-7_38.

Spoljašnje veze

[rstar-1] Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). „The R*-tree: an efficient and robust access method for points and rectangles”. Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 (PDF). str. 322. ISBN 0897913655. doi:10.1145/93597.98741.

[guttman-2] Guttman, Antonin (1984). „R-trees”. Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. str. 47. ISBN 0897911288. S2CID 876601. doi:10.1145/602259.602266.

[ang-tan-3] Ang, C. H.; Tan, T. C. (1997). „New linear node splitting algorithm for R-trees”. Advances in Spatial Databases. Lecture Notes in Computer Science. 1262. str. 337—349. ISBN 978-3-540-63238-2. doi:10.1007/3-540-63238-7_38.

[1]

[2]

[3]