Pređi na sadržaj

R* stabla

S Vikipedije, slobodne enciklopedije

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

[uredi | uredi izvor]
R*-stablo izgrađeno ponavljanjem unosa (u ELKI). Postoji malo preklapanje u ovom stablu, što rezultuje dobrim performansama upita. Crvene i plave MBR su indeksi strana, a zeleni su listovi.

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

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

Algoritam i kompleksnost

[uredi | uredi izvor]
  • 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 kompleksnija nego linearna strategija deljenja () R-stabala, ali manje kompleksna nego kvadratna strategija deljenja () za stranu veličine od 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 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

[uredi | uredi izvor]
  1. ^ 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. 
  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. 
  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. 

Spoljašnje veze

[uredi | uredi izvor]