R* стабла

Р*-стабла су варијанта Р-стабала која се користе за индексирање просторних информација. Р*-стабла имају незнатно већу цену конструкције од стандардних Р*-стабала, због могућности поновног уноса

података;али добијено дрво ће углавном имати бољe перформансе упита. Као и стандардно Р-стабло, Р*-стабло може складиштити и показивачке и просторне податке. Предложено је од стране Норберта Бекмана, Ханс–Питера Кригела, Ралфа Шнајдера, и Бернарда Сигера 1990. године.

Разлике између Р*-стабала и Р-стабала

Р*-стабло изграђено понављањем уноса (у ELKI). Постоји мало преклапање у овом стаблу, што резултује добрим перформансама упита. Црвене и плаве MBR су индекси страна, а зелени су листови.

Минимизација и покривености и преклапања је круцијална за перформансе Р-стабала. Преклапање значи да у подацима упита или уметања, више од једне гране стабла мора бити проширена (услед тога што се подаци деле у секције које се могу преклапати). Минимална покривеност унапређује перформансе орезивања, што дозвољава искључивање читавих страница из претраге чешће него иначе, у пракси за упите негативног домета.

Р*-стабло покушава да смањи оба, коришћењем комбинације прерађеног чвора подељеног алгоритма и концепта насилног поновног уметања у чвор преливања. Ово је базирано на запажању да су структуре Р-стабала врло осетљиве до границе у којој се уноси убацују, за тако изграђене структуре са појединачним уносом, (радије него структуре са више уноса одједном) је већа могућност да буду суб-оптималне. Брисање, и поновно убацивање уноса помаже им да „нађу“ место у стаблу које им више одговара него оригинална локација.

Када дође до преливања чвора, део уноса бива уклоњен из чвора и поново убачен у стабло. (У циљу избегавања неодређених каскада поновног убацивања уноса узрокованим наредног преливајућег чвора, рутина поновног уметања уноса може бити позвана само једном у сваком нивоу стабла приликом уношења било којег новог уноса). Ово има ефекат производње више добро-кластерованих група уноса у чворовима, смањујући покривеност чвора. Штавише сама дељења чвора су често одложена, што проузрокује раст просечног заузимања чвора. Поновно уметање може се посматрати као метод инкременталне оптимизације стабла, изазване чвором преливања.

Перформансе

• Побољшане издељене хеуристике производе стране које су више правоугаоне, и на тај начин бољe за многе апликације
• Метод поновног уноса оптимизује постојеће стабло, али му повећава и комплексност.
• Ефикасно подржава показивачке и просторне податке истовремено.

Ефекти различитих хеуристика дељења у бази са Немачким поштанским окрузима

• 
  Р-стабло са Гутмановим квадратним дељењем.
  Постоје многе стране које су проширене од истока до запада целом Немачком, и стране се доста преклапају. Ово није погодно за већину апликација, којима често треба само мала правоугаона област која се сече са многим пачићима.
• 
  Р-стабло са Анг-Тановим линеарним дељењем.
  Док се парчићи не распростиру као и са Гутманом, проблем пресецања утиче скоро на сваку страну листа. Стране листа се преклапају мало, али стране директоријума потпуно.
• 
  Р*-стабло тополошко дељење.
  Стране се преклапају јако мало јер Р*-стабло покушава да минимизује преклапање страна, и поновни уноси су још више оптимизовали стабло. Стратегија дељења такође не преферира парчиће, па су коначне стране су много више корисније за обичне апликације са мапама.

Алгоритам и комплексност

• Р*-стабло користи исти алгоритам за брисање и упит операција као и Р-стабло.
• Приликом уноса Р*-стабло користи комбиновану стратегију. За чворове листа, преклапање је минимизовано, док за унутрашње чворове проширења и област су минимизовани.
• Приликом дељења, Р*-стабла користе тополошко дељење, које бира издељену осу базирану на параметрима, затим минимизује преклапања.
• Додатно побољшаној стратегији дељења, Р*-стабло такође покушава да избегне дељења поновним уносом објеката и подстабала у стабло, инспирисано концептом балансирајућег Б-стабла.

Очигледно, најгори случај комплексности упита и брисања су идентична Р-стаблу. Стратегија уноса код Р*-стабала је са ${\mathcal {O}}(M\log M)$ комплекснија него линеарна стратегија дељења (${\mathcal {O}}(M)$) Р-стабала, али мање комплексна него квадратна стратегија дељења (${\mathcal {O}}(M^{2})$) за страну величине од $M$ објеката и има мало утицаја на укупну сложеност. Укупна сложеност уноса још увек може да се пореди са Р-стаблима: поновна убацивања утичу највише на једну грану стабла и тако ${\mathcal {O}}(\log n)$ поновних уноса, у поређењу са обављањем дељења на регуларном Р-стаблу. Све у свему, сложеност Р*-стабла је иста као и код регуларног Р-стабла. Имплементација потпуног алгоритма мора решити многе специјалне случајеве, и тесне ситуације које овде нису дискутоване.

Спољашње везе

• R-tree Demo Архивирано на сајту Wayback Machine (8. октобар 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