R* стабла

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

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

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

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

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

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

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

Перформансе

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

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

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

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

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

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

Референце

^ ^а ^б 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). стр. 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. стр. 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. стр. 337—349. ISBN 978-3-540-63238-2. doi:10.1007/3-540-63238-7_38.

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

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

[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). стр. 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. стр. 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. стр. 337—349. ISBN 978-3-540-63238-2. doi:10.1007/3-540-63238-7_38.

[1]

[2]

[3]