Išplėstinė paieška
 
 
 
Pradžia>Informatika>Struktūros pagrįstos objektų aibės dalinimu: R-medis
   
   
   
naudingas 0 / nenaudingas 0

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

  
 
 
123456789101112131415161718192021222324252627
Aprašymas

Įžanga. Struktūros pagrįstos objektų aibės dalinimu. R-medis. Paieška R-medyje. Objektų įterpimas ir pašalinimas R-medyje. R-medis. R-medžio pakavimas. R-medis.

Ištrauka

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 žingsniais. Pirmiausia atliekamas filtravimas (ang. filter step), kuriuo metu išrenkami tie objektai, kurių mbb tenkina užklausą. Tačiau tai, kad objekto mbb tenkina užklausą dar nereiškia, kad ir pats objektas tenkina užklausą. Todėl yra atliekamas antrasis žingsnis (ang. refinement step), kurio metu atrinkti objektai yra dar kartą peržiūrimi tikrinant ar tikroji objektų geometrija tenkina užklausą. Nors geometrijos tikrinimas užima daug laiko, bet jis yra taikomas tik mažam objektų skaičiui.

Įprastose duomenų bazėse efektyviam indeksavimui yra naudojami B-medžiai. Tačiau nėra paprasta juos pritaikyti erdvinių duomenų bazių indeksavimui. Norint sukurti erdvinių duomenų bazių indeksus reikia naudoti kitokius principus negu objektų rūšiavimas pagal jų koordinates. Visi SAM yra skirstomi į dvi grupes:

1) struktūros pagrįstos paieškos erdvės dalinimu (Space-driven structures). Šių metodų pagrindas – visos erdvės dalinimas į stačiakampes sritis nepriklausomai nuo objektų išsidėstymo. Objektai yra susiejami su sritimis pagal tam tikrus geometrinius kriterijus.
2) struktūros pagrįstos objektų aibės dalinimu (Data-driven structures). Priešingai nei pirmu atveju, skaidoma ne erdvė, o objektų aibė. Toks suskaidymas atspindi objektų pasiskirstymą erdvėje.

Struktūros pagrįstos objektų aibės dalinimu

R-medžiai yra erdvinių duomenų pasiekimo metodų šeima (Spatial Access Method - SAM). Jų kūrimas pagrįstas objektų aibės dalinimu į stačiakampes sritis priklausomai nuo jų išsidėstymo plokštumoje (angliškai jie vadinami data-driven metodais). R-medžio (taip pat kaip ir B-medžio) struktūra yra subalansuota ir hierarchinė. Medis sudarytas iš mazgų, kurie sujungti šakomis. Mazgai esantys žemiausiame lygyje yra vadinami lapais (angl. leaf). Subalansuota struktūra vadinamas toks duomenų pasiskirstymas mazguose, kai duomenų skaičius bet kuriuose dviejuose mazguose skiriasi nedaugiau kaip vienetu. Kiekvienas medžio mazgas (tiek vidinis, tiek lapas) yra saugomas disko puslapyje. Kitaip nei B-medžiai, kurie yra sukonstruoti naudojant vienos reikšmės raktus ir pagrįsti visiška tų raktų tvarka, R-medžiai suskirsto erdvę stačiakampiais atsižvelgdami į objektus. Su kiekvienu mazgu yra susietas stačiakampis, kuris pažymimas katalogo stačiakampiu (directory rectangle – dr). Katalogo stačiakampis yra minimalus stačiakampis, kuris apima visus objektus esančius jame. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2010-05-07
DalykasInformatikos referatas
KategorijaInformatika
TipasReferatai
Apimtis24 puslapiai 
Literatūros šaltiniai1
Dydis2.58 MB
AutoriusHuperis
Viso autoriaus darbų5 darbai
Metai2009 m
Klasė/kursas1
Mokytojas/DėstytojasProf. Romualdas Baušys
Švietimo institucijaVilniaus Gedimino Technikos Universitetas
FakultetasFundamentinių mokslų fakultetas
Failo pavadinimasMicrosoft Word Strukturos pagristos objektu aibes dalinimu R medis [speros.lt].doc
 

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Referatai
  • 24 puslapiai 
  • Vilniaus Gedimino Technikos Universitetas / 1 Klasė/kursas
  • Prof. Romualdas Baušys
  • 2009 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą