Бx-стабло

У информатици, Б^x стабло је засновано на Б+ стаблу и представља индексну струкутру за покретне објекте.

Структура индекса

Основна структура Б^x-стабла представља Б+ стабло унутар кога чворови служе као директоријуми и сваки чвор садржи показивач ка свом десном комшији. У претходној верзиији Б^x-стабла, листови су садржали локације индексирања покретног-објекта и одговарајуће време индексирања. У оптимизованој верзији, сваки унос у лист садржи идентификатор, брзину, једнодимензионалну вредност мапирања и последње ажурирано време објекта. Дистрибуција се повећава нечувањем положаја покретних објеката, јер се они добијају из мапираних вредности.

Коришћење Б+ стабла за покретне објекте

Пример Б^x-стабла са бројем партиција једнаким 2 са једним интервалом максималног ажурирања. У овом примеру, највише 3 партиције могу да постоје у исто време. После линеаризације, локација објекта унесена за време 0 је индексирана у партицији 0 са ознаком временског печата 0.5tmu, локације објекта ажуриране времена 0 на 0.5tmu су индексиране у партицији 1 са ознаком временског печата tmu, и тако даље(показано стрелицом). Како време пролази, понављајући први опсег истиче(осенчено подручје), а нови опсег се додаје(испрекидана линија).

Као и за друге индексе објеката у покрету, дводимензионално кретање објекта је моделовано као линеарна функција O = ((x, y), (vx, vy), t ), где су (x, y) и (vx, vy) локација и брзина објеката у датом временском тренутку t, нпр. време последњег ажурирања. Б+ стабло је структура за индексирање једнодимензионалних података. Како би се Б+ стабло усвојило као индекс покретног објекта, Б^x-стабло користи технику линеарности која помаже да се интегрише локација објекта за време t у једнодимензионалну вредност. Конкретно, објекти се прво класификују по времену ажурирања. За објекте из те класе, Б^x-стабло складисти њихове локације у датом тренутку које су процењене помоћу линеарне интрерполације. На тај начин Б^x-стабло чува доследан приказ свих објеката из исте класе без чувања времена ажурирања објеката.

Друго, простор је подељен мрежом и локација објекта је линеаризована унутар партиције према кривој која испуњава простор, нпр. Пеанова или Хилбертова крива.

Коначно, са комбинацијом броја партиције (временска информација) и линеарног реда (информација о локацији), објекат се индексира у Б^x-стабло једнодимензионалним кључем индекса Б^x вредност:

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

Овде је индекс партиција индекс партиција одређена временом ажурирања а xrep је вредност криве која попуњава простор позиције објекта у ундексном времену, $\left[X\right]_{2}$ означава бинарну вредност x, а “+” означава конкатенацију.

За дати објекат O ((7, 2), (-0.1,0.05), 10), tmu = 120, Б^x вредност за O може бити израчуната као што следи.

1. О је индексиран у партицији 0, као што је поменуто. Стога, партиција индекса = (00)₂.
2. Позиција О на етикети временског пецата партиције 0 је (1,5).
3. Користећи Z криву са редом = 3, Z-вредност од O, нпр, xrep је (010011)₂.
4. Конкатенацијом индекс партиције и xrep-а, Б^x вредност је (00010011)₂=19.

Унос, ажурирање и брисање

Када је дат нови објекат, његов индексни кључ се израчунава и уноси у Б^x-стабло као у Б+ стабло. Ажурирање се састоји од брисања које прати нови унос. Задатак помоћне структуре је да чува последњи кључ сваког индекса како би објекат био обрисан тражењем кључа. Индексни кључ се израчунава пре утицаја на стабло. На овај начин Б^x-стабло директно задржава добра својства Б+ стабла, и постиже ефикасне перформансе ажурирања.

Упити

Опсег упита

Опсег упита преузима све објекте чија локација потпада под правоугаони опсег $q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)$ у време $tq$ не пре садашњег времена.

Б^x-стабло користи технику проширења прозора упита како би одговорило на упите. Пошто Б^x-стабло чува локацију објекта нешто после ажурирања времена, проширење обухвата два случаја: локација се мора или вратити на раније време или напредовати на касније. Главна идеја је да се прозор упита увећа како би обухватао све објекте чија позиција није у оквиру прозора упита на његовој ознаци временског печата, али ће ући у прозор упита на временски печат упита.

Након проширења, партиције Б^x-дрвета треба да се укрсте како би пронашле објекте који спадају у проширени прозор упита. У свакој партицији, употреба криве која испуњава простор значи да опсег упита у природном, дводимензионалном простору постаје скуп опсега упита у трансформисаном, једнодимензионалном простору.

Како би се избегао превелики опсег упита након експанзије у искошеном скупу података, постоји оптимизација алгоритма упита, која побољшава ефикасност упита избегавајући непотребно проширење истог.

K најближи сусед упита

K најближи сусед упита је израчунат итеративним представљањем опсега упита са инкрементало увећаним регионом за претраживање док се к одговора не добије. Друга могућност је потражити сличне идеје о упитима у The iDistance Technique.

Остали упити

Опсег упита и К најближи сусед упита алгоритам може лако да се прошири како би подржавао интервале упита, континуиране упите, итд.

Прилагођавање релационе базе података за смештај покретних објеката

Пошто је Б^x-стабло индекс изграђен над Б+ стаблом, све операције у Б^x-стаблу, укључујући унос, брисање и тражење су исте као у Б+ стаблу. Нема потребе да се имплементације ових операција мењају. Једина разлика је спровођење поступка извођења индексног кључа као ускладиштена процедура у постојећем ДМБС. Стога се Б^x-стабло лако може интегрисати у постојећи ДМБС без додиривања кернела.

SРADE је управљачки систем за покретне објекте изграђен на врху популарне релационе базе података MySQL, која користи Б^x-стабло за индексирање објеката. У реализацији, подаци о покретном објекту се трансформишу и чувају директно у MySQL-у, упити се транформишу у стандардне SQL извештаје који су ефикасно обрађени у релационој бази. Најважније, све то се постиже уредно и независно без мешања у MySQL кернел.

Подешавање перформанси

Могући проблеми са искошеним подацима

Б^x стабло користи мрежу за просторно дељење док мапира дводимензионалне локације у једнодимензионални кључ. Ово може довести до смањења перформанси како упита тако и радњи ажурирања док се ради са искошеним подацима. Ако је мрежна ћелија превелика, у ћелији се налазе многи објекти. Пошто индекс не разликује објекте у ћелији, у основи Б+ стабла налазиће се неки преоптерећени чворови. Постојање пренатрпаних ћелија не само да нарушавају равнотежу стабла, већ повећавају трошкове ажурирања. Што се тиче упита, за дату област упита, велике ћелије остварују више лажних детекција и време обраде. Са друге стране, ако је простор подељен финијом мрежом, односно са мање ћелија, свака ћелија садржи неколико објеката. Тешко долази до преоптерећења, па је време ажурирања минимизовано. Мање лажних детекција се преузима у упиту. Међутим, треба претражити већи број ћелија. Повећање броја ћелија такође повећава оптерећење упита.

Подешавање индекса

ST²Б-стабло уводи оквир за самостално подешавање перформанси код подешавања перформанси Б^x-стабла када се бави искошеним подацима у простору и променом података времена. С намером да обрађује искошене податке у простору, ST²Б-стабло дели цео простор у рејоне са различитом збијеношћу објеката користећи скуп референтних тачака. Сваки рејон користи посебну мрежу чија је ћелија одређена збијеношћу објеката унутар ћелије.

Б^x-стабло има многе партиције које се односе на различите временске интервале. Како време пролази, свака партиција се скупља и шири наизменично. ST²Б-стабло користи ову функцију за подешавање индекса у мрежи, да би прилагодио дељење простора како би се простор прилагодио временом на промене података. Нарочито, како се партиција скупља до испражњења и почиње да расте, бира нови сет референтних тачака и нову мрежу за сваку референтну тачку према њиховој збијености података. Подешавање се заснива на најновијим статистичким подацима прикупљеним током одређеног временског периода, тако да дељење партиције треба највише да одговара последњем уносу података. На тај начин ST²Б-стабло треба да минимизује ефекат који је настао изобличавањем података у простору и промене података настале временом.

Видите такође

• B+ tree
• Hilbert curve
• Z-order (curve)