Struktūros pagrįstos objektų aibės dalinimu: R-medis

Įžanga
Tam, kad efektyviai apdoroti erdvines užklausas reikia naudoti specifinius duomenų pasiekimo metodus, kurie remiasi tam tikra duomenų struktūra, vadinama indeksu. Šie metodai pagreitina duomenų išrinkimą dėl to, kad apdorojant užklausą reikia peržvelgti mažiau objektų.
Erdvinių užklausų pavyzdžiais gali būti taško užklausos ir lango užklausos. Taško užklausos atveju ieškomi objektai, kurie savyje turi tą tašką, o lango užklausos atveju – objektai, kurie bent dalinai įeina (overlap) į duotą sritį.
Erdvinių užklausų apdorojimas reikalauja sudėtingų geometrinių operacijų, kurias atlikti reikia daug laiko. Norint įvykdyti tokias operacijas reikėtų tikrinti visus objektus (kurių dažniausiai yra labai daug) ar jie atitinka užklausos sąlygą.
Norint įvykdyti erdvinę užklausą nenaudojant indeksų reikėtų paeiliui užkrauti ir tikrinti visus didelių duomenų masyvų objektus. Tam reikėtų atlikti daug duomenų įvedimo/išvedimo operacijų iš išorinių kietųjų diskų ir pakartotinai skaičiuoti ir įvertinti sudėtingus geometrinius predikatus (logines funkcijas). Tiek kreipimosi į diską ir duomenų nuskaitymo/įrašymo operacijos, tiek geometrinių algoritmų apskaičiavimas yra palyginti lėtos operacijos. Taigi norint greičiau įvykdyti erdvinę užklausą reikia kaip galima labiau sumažinti objektų, kurie turi būti apdorojami, aibę. Tam ir yra naudojami erdvinių duomenų pasiekimo metodai (angl. Spatial access methods arba SAM). Šie metodai įgalina sumažinti apdorojimo laiką logaritmiškai ar netgi dar mažiau palyginti su duomenų masyvo dydžiu. Šie metodai naudoja struktūrą vadinamą erdviniu indeksu (angl. spatial index), o duomenų masyvas, kuriam yra sukurtas indeksas, vadinamas indeksuotu.
Erdvinėje duomenų bazėje esančių objektų geometrinės savybės (formos) gali būti sudėtingos. Todėl vietoj to, kad būtų indeksuojami patys objektai, yra indeksuojami geometriniai artiniai. Dažniausiai tokia apytikslė forma yra stačiakampis apimantis objektą, kuris yra vadinamas minimaliu apimančiu stačiakampiu (angl. minimal bounding box arba sutrumpintai mbb). Naudojant tokį artinį kaip raktą vietoj tikros objekto geometrinės formos erdvinio indekso kūrime yra sutaupoma laiko, nes kreipiantis į indekso elementus nereikia atlikti sudėtingų algoritmo geometrinės formos apskaičiavimui, o taip pat supaprastėja indekso kūrimas.
Kai turime suindeksuotą duomenų masyvą, erdvinė užklausa yra atliekama dviem...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!