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.

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

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

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

Spoljašnje veze

• R-tree Demo Arhivirano na sajtu Wayback Machine (8. oktobar 2014)
• The TPIE Library contains a C++ R* tree implementation
• A header-only C++ R* Tree Implementation
• C++ implementation are in the Spatial Index Library
• Boost.Geometry library containing R*-tree implementation