R* stabla

Из Википедије, слободне енциклопедије

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

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

Разлике између Р*-стабала и Р-стабала[уреди]

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

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

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

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

Перформансе[уреди]

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

Алгоритам и комплексност[уреди]

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

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

Референце[уреди]

  1. ^ а б doi: 10.1145.2F93597.98741
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  2. ^ doi: 10.1145/602259.602266
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  3. ^ doi: 10.1007/3-540-63238-7_38
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand

Спољашње везе[уреди]