Bx-stablo

U informatici, B^x stablo je zasnovano na B+ stablu i predstavlja indeksnu strukutru za pokretne objekte.

Struktura indeksa[uredi | uredi izvor]

Osnovna struktura B^x-stabla predstavlja B+ stablo unutar koga čvorovi služe kao direktorijumi i svaki čvor sadrži pokazivač ka svom desnom komšiji. U prethodnoj verziiji B^x-stabla, ^[1] listovi su sadržali lokacije indeksiranja pokretnog-objekta i odgovarajuće vreme indeksiranja. U optimizovanoj verziji,^[2] svaki unos u list sadrži identifikator, brzinu, jednodimenzionalnu vrednost mapiranja i poslednje ažurirano vreme objekta. Distribucija se povećava nečuvanjem položaja pokretnih objekata, jer se oni dobijaju iz mapiranih vrednosti.

Korišćenje B+ stabla za pokretne objekte[uredi | uredi izvor]

Primer B^x-stabla sa brojem particija jednakim 2 sa jednim intervalom maksimalnog ažuriranja. U ovom primeru, najviše 3 particije mogu da postoje u isto vreme. Posle linearizacije, lokacija objekta unesena za vreme 0 je indeksirana u particiji 0 sa oznakom vremenskog pečata 0.5tmu, lokacije objekta ažurirane vremena 0 na 0.5tmu su indeksirane u particiji 1 sa oznakom vremenskog pečata tmu, i tako dalje(pokazano strelicom). Kako vreme prolazi, ponavljajući prvi opseg ističe(osenčeno područje), a novi opseg se dodaje(isprekidana linija).

Kao i za druge indekse objekata u pokretu, dvodimenzionalno kretanje objekta je modelovano kao linearna funkcija O = ((x, y), (vx, vy), t ), gde su (x, y) i (vx, vy) lokacija i brzina objekata u datom vremenskom trenutku t, npr. vreme poslednjeg ažuriranja. B+ stablo je struktura za indeksiranje jednodimenzionalnih podataka. Kako bi se B+ stablo usvojilo kao indeks pokretnog objekta, B^x-stablo koristi tehniku linearnosti koja pomaže da se integriše lokacija objekta za vreme t u jednodimenzionalnu vrednost. Konkretno, objekti se prvo klasifikuju po vremenu ažuriranja. Za objekte iz te klase, B^x-stablo skladisti njihove lokacije u datom trenutku koje su procenjene pomoću linearne intrerpolacije. Na taj način B^x-stablo čuva dosledan prikaz svih objekata iz iste klase bez čuvanja vremena ažuriranja objekata.

Drugo, prostor je podeljen mrežom i lokacija objekta je linearizovana unutar particije prema krivoj koja ispunjava prostor, npr. Peanova ili Hilbertova kriva.

Konačno, sa kombinacijom broja particije (vremenska informacija) i linearnog reda (informacija o lokaciji), objekat se indeksira u B^x-stablo jednodimenzionalnim ključem indeksa B^x vrednost:

B^{x}value\left(O,t\right)=\left[indexpartition\right]_{2}+\left[xrep\right]_{2}

Ovde je indeks particija indeks particija određena vremenom ažuriranja a xrep je vrednost krive koja popunjava prostor pozicije objekta u undeksnom vremenu, $\left[X\right]_{2}$ označava binarnu vrednost x, a “+” označava konkatenaciju.

Za dati objekat O ((7, 2), (-0.1,0.05), 10), tmu = 120, B^x vrednost za O može biti izračunata kao što sledi.

O je indeksiran u particiji 0, kao što je pomenuto. Stoga, particija indeksa = (00)₂.
Pozicija O na etiketi vremenskog pecata particije 0 je (1,5).
Koristeći Z krivu sa redom = 3, Z-vrednost od O, npr, xrep je (010011)₂.
Konkatenacijom indeks particije i xrep-a, B^x vrednost je (00010011)₂=19.

Unos, ažuriranje i brisanje[uredi | uredi izvor]

Kada je dat novi objekat, njegov indeksni ključ se izračunava i unosi u B^x-stablo kao u B+ stablo. Ažuriranje se sastoji od brisanja koje prati novi unos. Zadatak pomoćne strukture je da čuva poslednji ključ svakog indeksa kako bi objekat bio obrisan traženjem ključa. Indeksni ključ se izračunava pre uticaja na stablo. Na ovaj način B^x-stablo direktno zadržava dobra svojstva B+ stabla, i postiže efikasne performanse ažuriranja.

Upiti[uredi | uredi izvor]

Opseg upita[uredi | uredi izvor]

Opseg upita preuzima sve objekte čija lokacija potpada pod pravougaoni opseg $q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)$ u vreme $tq$ ne pre sadašnjeg vremena.

B^x-stablo koristi tehniku proširenja prozora upita kako bi odgovorilo na upite. Pošto B^x-stablo čuva lokaciju objekta nešto posle ažuriranja vremena, proširenje obuhvata dva slučaja: lokacija se mora ili vratiti na ranije vreme ili napredovati na kasnije. Glavna ideja je da se prozor upita uveća kako bi obuhvatao sve objekte čija pozicija nije u okviru prozora upita na njegovoj oznaci vremenskog pečata, ali će ući u prozor upita na vremenski pečat upita.

Nakon proširenja, particije B^x-drveta treba da se ukrste kako bi pronašle objekte koji spadaju u prošireni prozor upita. U svakoj particiji, upotreba krive koja ispunjava prostor znači da opseg upita u prirodnom, dvodimenzionalnom prostoru postaje skup opsega upita u transformisanom, jednodimenzionalnom prostoru. ^[1]

Kako bi se izbegao preveliki opseg upita nakon ekspanzije u iskošenom skupu podataka, postoji optimizacija algoritma upita,^[3] koja poboljšava efikasnost upita izbegavajući nepotrebno proširenje istog.

K najbliži sused upita[uredi | uredi izvor]

K najbliži sused upita je izračunat iterativnim predstavljanjem opsega upita sa inkrementalo uvećanim regionom za pretraživanje dok se k odgovora ne dobije. Druga mogućnost je potražiti slične ideje o upitima u The iDistance Technique.

Ostali upiti[uredi | uredi izvor]

Opseg upita i K najbliži sused upita algoritam može lako da se proširi kako bi podržavao intervale upita, kontinuirane upite, itd.^[2]

Prilagođavanje relacione baze podataka za smeštaj pokretnih objekata[uredi | uredi izvor]

Pošto je B^x-stablo indeks izgrađen nad B+ stablom, sve operacije u B^x-stablu, uključujući unos, brisanje i traženje su iste kao u B+ stablu. Nema potrebe da se implementacije ovih operacija menjaju. Jedina razlika je sprovođenje postupka izvođenja indeksnog ključa kao uskladištena procedura u postojećem DMBS. Stoga se B^x-stablo lako može integrisati u postojeći DMBS bez dodirivanja kernela.

SRADE^[4] je upravljački sistem za pokretne objekte izgrađen na vrhu popularne relacione baze podataka MySQL, koja koristi B^x-stablo za indeksiranje objekata. U realizaciji, podaci o pokretnom objektu se transformišu i čuvaju direktno u MySQL-u, upiti se tranformišu u standardne SQL izveštaje koji su efikasno obrađeni u relacionoj bazi. Najvažnije, sve to se postiže uredno i nezavisno bez mešanja u MySQL kernel.

Podešavanje performansi[uredi | uredi izvor]

Mogući problemi sa iskošenim podacima[uredi | uredi izvor]

B^x stablo koristi mrežu za prostorno deljenje dok mapira dvodimenzionalne lokacije u jednodimenzionalni ključ. Ovo može dovesti do smanjenja performansi kako upita tako i radnji ažuriranja dok se radi sa iskošenim podacima. Ako je mrežna ćelija prevelika, u ćeliji se nalaze mnogi objekti. Pošto indeks ne razlikuje objekte u ćeliji, u osnovi B+ stabla nalaziće se neki preopterećeni čvorovi. Postojanje prenatrpanih ćelija ne samo da narušavaju ravnotežu stabla, već povećavaju troškove ažuriranja. Što se tiče upita, za datu oblast upita, velike ćelije ostvaruju više lažnih detekcija i vreme obrade. Sa druge strane, ako je prostor podeljen finijom mrežom, odnosno sa manje ćelija, svaka ćelija sadrži nekoliko objekata. Teško dolazi do preopterećenja, pa je vreme ažuriranja minimizovano. Manje lažnih detekcija se preuzima u upitu. Međutim, treba pretražiti veći broj ćelija. Povećanje broja ćelija takođe povećava opterećenje upita.

Podešavanje indeksa[uredi | uredi izvor]

ST²B-stablo^[5] uvodi okvir za samostalno podešavanje performansi kod podešavanja performansi B^x-stabla kada se bavi iskošenim podacima u prostoru i promenom podataka vremena. S namerom da obrađuje iskošene podatke u prostoru, ST²B-stablo deli ceo prostor u rejone sa različitom zbijenošću objekata koristeći skup referentnih tačaka. Svaki rejon koristi posebnu mrežu čija je ćelija određena zbijenošću objekata unutar ćelije.

B^x-stablo ima mnoge particije koje se odnose na različite vremenske intervale. Kako vreme prolazi, svaka particija se skuplja i širi naizmenično. ST²B-stablo koristi ovu funkciju za podešavanje indeksa u mreži, da bi prilagodio deljenje prostora kako bi se prostor prilagodio vremenom na promene podataka. Naročito, kako se particija skuplja do ispražnjenja i počinje da raste, bira novi set referentnih tačaka i novu mrežu za svaku referentnu tačku prema njihovoj zbijenosti podataka. Podešavanje se zasniva na najnovijim statističkim podacima prikupljenim tokom određenog vremenskog perioda, tako da deljenje particije treba najviše da odgovara poslednjem unosu podataka. Na taj način ST²B-stablo treba da minimizuje efekat koji je nastao izobličavanjem podataka u prostoru i promene podataka nastale vremenom.

Vidite takođe[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ ^a ^b Christian S. Jensen, Dan Lin, and Beng Chin Ooi. Query and Update Efficient B+tree based Indexing of Moving Objects. In Proceedings of 30th International Conference on Very Large Data Bases (VLDB), pages 768-779, 2004.
^ ^a ^b Dan Lin. Indexing and Querying Moving Objects Databases, PhD thesis, National University of Singapore, 2006.
^ Jensen, C.S., D. Tiesyte, N. Tradisauskas, Robust B+-Tree-Based Indexing of Moving Objects, in Proceedings of the Seventh International Conference on Mobile Data Management, Nara, Japan, 9 pages, May 9–12, 2006.
^ SpADE Arhivirano na sajtu Wayback Machine (2. januar 2009): A SPatio-temporal Autonomic Database Engine for location-aware services.
^ Su Chen, Beng Chin Ooi, Kan-Lee. Tan, and Mario A. Nacismento, ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree for Moving Objects Arhivirano na sajtu Wayback Machine (11. jun 2011). In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD), page 29-42, 2008.

Šablon:CS-Trees

[Jensen2004-1] Christian S. Jensen, Dan Lin, and Beng Chin Ooi. Query and Update Efficient B+tree based Indexing of Moving Objects. In Proceedings of 30th International Conference on Very Large Data Bases (VLDB), pages 768-779, 2004.

[Lin-2] Dan Lin. Indexing and Querying Moving Objects Databases, PhD thesis, National University of Singapore, 2006.

[3] Jensen, C.S., D. Tiesyte, N. Tradisauskas, Robust B+-Tree-Based Indexing of Moving Objects, in Proceedings of the Seventh International Conference on Mobile Data Management, Nara, Japan, 9 pages, May 9–12, 2006.

[4] SpADE Arhivirano na sajtu Wayback Machine (2. januar 2009): A SPatio-temporal Autonomic Database Engine for location-aware services.

[5] Su Chen, Beng Chin Ooi, Kan-Lee. Tan, and Mario A. Nacismento, ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree for Moving Objects Arhivirano na sajtu Wayback Machine (11. jun 2011). In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD), page 29-42, 2008.

[1]

[2]

[3]

[4]

[5]