Хилбертово Р-стабло
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Хилбертово Р-стабло, варијанта Р-стабла је индикатор за вишедимензионалне објекте као што су линије, региони, 3-D објекти или високо-димензионални објекти засновани на параметарским облицима. Може се посматрати као проширење Б+-стабла за вишедимензионалне објекте. Перформансе Р-стабла зависе од квалитета алгоритма који групише правоугаонике података на чвору. Хилбертово Р-стабло користи просторно-пуне криве, а посебно Хилбертове криве, како би на правоугаонике података наметнуо линеаран редослед. Постоје две врсте Хилбертових Р-стабала, један за статичке, а један за динамичке базе података. У оба случаја Хилбертове просторно-пуне криве се користе ради псотизања бољег редоследа вишедимензионалних објеката на чвору. Овај редослед мора да буде "добар", у том смислу да групише заједно 'сличне' правоугаонике података, како би се смањио простор и обим добијеног. Пакована Хилбертова Р-стабла су погодна за статичке базе података у којима је ажурирање података веома ретко, или уопште није присутно. Динамичко Хилбертово Р-стабло је погодно за динамичке базе података где се уметање, брисање или ажурирање може постићи у реалном времену. Штавише, динамичко Хилбертово Р-стабло употребљава флексибилан механизам одложеног раздвајања, како би повећао степен искоришћености простора. Сваки чвор има добро дефинисан скуп чворова рођака. Прилагођавањем политике поделе Хилбертово Р-стабло може постићи жељени степен искоришћености простора. Ово се постиже планирањем уређености чворова на Р-стаблу. Хилбертово Р-стабло сортира правоугаонике према Хилбертовој вредности центра правоугаоника. Насупрот Хилбертовом Р-стаблу, друге варијанте Р-стабла немају контролу над степеном искоришћености простора.
Основна идеја[уреди | уреди извор]
Иако је следећи пример за статичко окружење, објашњава интуитивне принципе за добар дизајн Р-стабла. Ови принципи важе и за статичке и за динамичке базе података. Роуссопоулос и Леифкер су предложили метод за изградњу пакованог Р-стабла који постиже степен од скоро 100% искоришћености простора. Идеја је сортирање података на x или y координату једног угла правоугаоника. Сортирање на било коју од четири координате даје сличан резултат. У овом случају, тачке или правоугаоници су сортирани на x координату најнижег левог угла правоугаоника. У дискусији која следи, Роуссопоулос-ов и Леифкер-ов метод се посматра као ниско x паковано Р-стабло. Сортирана листа правоугаоника се претражује; узастопни правоугаоници се додељују истом листу Р-стабла све док је тај чвор пун; тада се креира нови лист и претраживање сортиране листе се наставља. Тако ће чворови резултујућег Р-стабла бити у целости упаковани, са могућим изузетком последњег чвора на сваком нивоу. Тако је проценат искоришћености ≈100%. Виши нивои стабла су креирани на сличан начин. Фигура 1 наглашава проблем ниско x пакованог Р-стабла. Слика 1[десно] паказује листове Р-стабла које ће ниско x паковани метод направити за тачке Слике 1 [лево]. Чињеница да добијени родитељи покривају малу област објашњава зашто ниско x паковани метод Р- стабла постиже одличне перформансе за тачке упита. Међутим, чињеница да родитељи имају велики опсег објашњава деградацију перформансе за предео упита. Ово је у складу са аналитичким формулама за перформансе Р-стабла. .[1] Интуитивно гледано, алгоритам паковања би идејно требао доделити оближње тачке истом листу. Игнорисање y координате у ниско x пакованом Р-стаблу прети да наруши ово емпирично правило.
Слика 1: [лево] 200 тачака равномерно распоређених; [десно] минимални гранични правоугаоници чворова генерисани ‘ниско x пакованим ’ алгоритмом за Р-стабло
Овај одељак описује две варијанте Хилбертовог Р-стабла. Први индикатор је погодан за статичке базе података у којима је ажурирање веома ретко или није присутно уопште. Чворови резултујућег Р-стабла ће бити целовито упаковани, са могућом изнимком последњег чвора на сваком нивоу. Тако је степен употребе простора ≈100%; ова структура се назива паковано Хилбертово Р-стабло. Други индикатор се наyива динамичко Хилбертово Р-стабло, подржава уметање и брисање; погодан је за динамичко окружење.
Пакована Хилбертова Р-стабла[уреди | уреди извор]
У наставку је дат кратак увод не тему Хилбертове криве. Основна Хилбертова крива на мрежи 2x2, означена са Х1 је показана на слици 2. Како би извели криву реда и, свако теме основне криве је замењено кривом реда и – 1, што може бити адекватно ротирано и/или рефлектовано. Слика 2 такође показује Хилбертове криве реда два и три. Кад ред криве тежи бесконачности, као друге просторно пуне криве, резултујућа крива је структурално фрактална, са димензијом 2.[1][2] Хилбертова крива може бити генерализована за виши степен димензионалности. Алгоритми за цртање 2-димензионе криве датог реда може бити нађен на[3] и[2] Алгоритам за већу димензионалност је дат на.[4] Путања просторно пуне криве намеће линеарни редослед на тачкама мреже; ова путања може бити израчуната пратећи путању криве са почетком у једном крају, а завршетком у другом крају криве. Вредности координата могу бити израчунате у свакој тачки. Слика 2 показује један такав редослед за мрежу 4x4. На пример, тачка (0,0) на Х2 криви има Хилбертову вредност 0, док тачка (1,1) има Хилбертову вредност 2.
Слика 2: Хилберт-ове криве реда 1, 2 и 3
Хилбертова крива намеће линеаран редослед правоугаоника података, а затим прелази на сортирану листу, додељујући скуп од C правоугаоника сваком чвору Р-стабла. Крајњи резултат је тај да ће скуп правоугаоника података на истом чвору бити близу један другог према линеарном редоследу и највероватниј у родном простору. Дакле, добијени чворови Р-стабла ће имати мања подручија. Слика 2 илуструје разлоге због којих ће методе засноване на Хилбертовом Р-стаблу имати добру перформансу. Подаци се састоје од тачака (исте тачке које су дате и на слици 1). Груписањем тачака према њиховој Хилбертовој вредности, МГП добијених чворова Р-стабла имају тенденцију да буду мали квадрати налик правоугаоницима. Ово указује да ће чворови највероватније имати малу површину и мале параметре. Мала површина доноси добре перформансе за упите тачака; мала површина и мали параметри доносе добру перформансу за веће упите.
Алгоритам Хилбертовог паковања[уреди | уреди извор]
(пакује правоугаонике на Р-стабло)
Корак 1. Рачуна Хилбертову вредност за сваки правоугаоник податка
Корак 2. Сортира правоугаонике података по узлазном поретку Хилбертових вредности
Корак 3. /* Прави листове (ниво л=0) */
- Wхиле (има још правоугаоника)
- генериши нови чвор Р-стабла
- додели следећи C правоугаоник овом чвору
Корак 4. /* Направи чворове на вишем нивоу (л + 1) */
- Wхиле (док су > 1 чвора на новоу л)
- сортирај чворове на нивоу л ≥ 0 на основу узлазног поретка времена потребног за креирање
- понови корак 3
Претпоставка је да су подаци статички или да је фрекфенција модификације ниска. Ово је једноставна херуистика за изградњу Р-стабла са степеном искоришћености простора од 100% што ће истовремено имати најбоље могуће време одговора.
Динамичка Хилбертова Р-стабла[уреди | уреди извор]
Перформансе Р-стабла зависе од квалитета алгоритма који групишу правоугаонике података на чвор. Хилбертова Р-стабла користе просторно пуне криве, конкретно Хилбертову криву, како би наметнула линеарни редослед на правоугаонике података.
Хилбертова вредност правоугаоника се дефинише као вредност његовог центра.
Структура стабла[уреди | уреди извор]
Хилбертово Р-стабло има следећу структуру. Лист садржи највише Cл улаза, облика (Р, обј _ид) где је Cл капацитет листа, а Р је МГП(минимални гранични правоугаоник) реалног објекта. (xниско, xвисоко, yниско, yвисоко) и обј-ид је показивач на објекат који садржи записник описа тог објекта. Главна разлика измедју Хилбертовог Р-стабла и Р*-стабла[5] је та да чворови који нису листови садрзе информације о "ЛХВ"(највећа Хилбертова вредност). Дакле, чвор који није лист у Хилбертовом Р-стаблу садржи највише Cн улаза облика (Р, птр, НХВ) где је Cн капацитет чвора који није лист, Р је "МГП" који обухвата сву децу тог чвора, "птр" је показивач на дете чвора, "НХВ" је највећа Хилбертова вредност између правоуганика података обухваћених са Р. Треба приметити да чвор који није лист бира једну од Хилбертових вредности његове деце и поставља је за сопствену "НХВ" вредност. Не постоји додатна цена за израчунавање Хилбертових вредности МГП-а за чворове који нису листови. Слика 3 илуструје неке правоукаонике организоване у Хилбертовим Р-стаблима. Хилбертове вредности центра су бројеви близу 'x' симбола(приказује се само за чвора претка 'II')."НХВ" су приказани у [заградама]. Слика 4 приказује како се стабло са слике 3 чува на диску. Садржаји чвора претка 'II' су приказани са више детаља. Сваки правоуганик података у чвору 'I' има Хилбертову вредност в≤33.
Слика 3: илуструје неке правоукаонике организоване у Хилбертовим Р-стаблима. (Хилбертове вредности и НХВ су приказане у заградама) Обично Р-стабло дели чвор на два дела уколико дође до "преливања" на том чвору, правећи 2 нова чвора од првобитног. Ова политика се зове 1-на-2 политика цепања. Такође је могуће да се одложи расцеп, чекајући да се два чвора претворе у три. Уочите да је ово слично са Б*-политиком цепања стабла. Овај метод се зове 2-на-3 политика цепања. Генерално, ово се може проширити на с-на-(с+1) политика цепања, где је с наређење за политику цепања. За имплементацију политике цепања, "преливени" чвор гура неке од његових улаза на с-1 рођаке. Алгоритми за претраживање, убацивање и "руковање преливеним" су описани детајно у даљем тексту.
Тражење[уреди | уреди извор]
Алгоритам тражења је сличан алгоритмима тражења коришћеним у другим варијантама Р-стабла. Почевши од корена, спушта се низ стабло и испитује све чворове који секу правоугаонике упита. На нивоу листа, пријављује све улазе који секу прозоре w упита као квалификоване ставке података.
Алгоритам Тражење(корен, правоугаоник w):
С1. Тражи чворове који нису листови:
- Зови Тражи за сваки улаз чији МГП сече прозор w упита.
- Пријави као кандидате све улазе који секу прозор w упита.
Фигура 4: Структура фајла за Хилбертово Р-стабло
Уметање[уреди | уреди извор]
За уметање новог правоугаоника р у Хилбертово Р-стабло, Хилбертова вредност х од центра новог правоугаоника се користи као кључ. На сваком нивоу изабран је чвор са најмањом НХВ вредношћу већом од х. Када је досегнут лист, правоугаоник р је уметнут по одговарајућем распореду према х. Након што је нови правоугаоник уметнут у лист Н, позвано је подеси стабло како би поправило вредности МГП и ЛХВ на чворовима већег нивоа.
Алгоритам Уметни(корен, правоугаоник р): /* Убацује нови правоугаоник р у Хилбертово Р-стабло. х је Хилбертова вредност правоугаоника*/
И1. Пронађи погодан лист.:
- Позови Изабери_лист(р, х) како би изабрао лист L у који ће бити смештен р.
И2. Убаци р у лист L:
- Ако L има празан прорез, убаци р у L на одговарајућем месту према Хилбертовом реду и врати се.
- Ако је L пуно, позови Руковање_преливеним(L,р), што ће вратити нови лист ако је раздвајање било неизбежно.
И3. Пропагирати промене нагоре:
- Формирати скуп С који садржи L, његове рођаке
- и нови лист (ако постоји)
- Призови подеси_стабло(С).
И4. Направи стабло да буде више:
- Ако је пропагација раздвајања чворова довела до поделе корена, направи
- нови корен чија су деца два резултујућа чвора.
Алгоритам Изабери_Лист(правоугаоник р, инт х):
/* Враћа лист на који ће сместити нови правоугаоник р. */
Ц1. Иницијализација:
- Постави Н да буде корен.
Ц2. Провера листа:
- Ако је Н корен, врати Н.
Ц3. Изабери подстабло:
- Ако је Н није лист, изабери улаз (Р, птр, НХВ)
- са минималном НХВ вредношћу која је већа од х.
Ц4. Спуштати се док се не дође до листа:
- Постави Н на чвор означен са птр и понови од Ц2.
Алгоритам Подеси_стабло(скуп С):
/* С је скуп чворова који садржи ажурирани чвор, његове рођаке (ако је дошло до преливнања) и најновији
направљен чвор НН (ако је дошло до раздвајања). Рутина се пење од нивоа листа према корену, подешавајући МГП анд НХВ чворова који покривају чворове у С. Пропагира раздвајање (ако постоји) */
А1. Ако се досегне ниво корена, стани.
А2. Пропагиран чвор се дели навише:
- Нека Нп буде родитељ од Н.
- Ако је Н било подељено нека НН буде нови чвор.
- Убаци НН у Нп по тачном распореду према Хилбертовој
- вредности ако има простора. Иначе позови Руковање_преливеним(Нп , НН ).
- Ако је Нп подељено, нека ПП постане нови чвор.
А3. Прилагоди МГП и НХВ на нивоу родитеља:
- Нека П буде скуп родитеља за чворове у С.
- Прилагоди одговарајуће МГП и НХВ чворова у П.
А4. Пређи на следећи ниво:
- Нека С постане скуп родитеља П, са
- НН = ПП, ако је Нп подељено.
- понови од А1.
Брисање[уреди | уреди извор]
У Хилбертовом Р-стаблу, нема потребе за поновним убацивањем чворова сирочади кад год дође до преливања чвора оца. Уместо тога, могу се позајмити кључеви од чворова са истим оцем, или се преливен чвор спаја са чворовима са којима дели оца. Ово је могуће јер чворови имају јасан поредак (према највећој Хилбертовој вредност); насупрот томе, у Р-стаблима не постоји такав концепт за чворове са истим оцем. Приметимо да операције брисања захтевају с сарађујућих чворова са истим оцем, до операције убацивања захтевају с-1 чвор са истим оцем. Алгоритам Обриши(р): Д1. Наћи чвор домаћина: Извршити претрагу да би се нашао лист који садржи р. Д2. Избрисати р: Уклонити р из чвора L. Д3. Ако L прелива Позајмити неке садржаје из с сарађујућих чворова са истим оцем Ако су сви чворови са истим оцем спремни да преливају спојити с+1 чвор подесити резултујуће чворове. Д3. Подесити МГП и НХВ у родитељским нивоима Направити скуп С који садржи чвор L и његове сарађујуће чворове са истим оцем (ако је дошло до преливања). Позвати Прилагоди_стабло(С).
Руковање преливеним[уреди | уреди извор]
Алгоритам за руковање преливеним у Хилбертовом Р-стаблу третира преливене чворове или преношењем неких садржаја у једно од с-1 сарађујућих чворова са истим оцем, или делећи с чворова у с+1 чвор.
Алгоритхм Руковање_преливеним(чвор Н, правоугаоник р):
/* врати нови чвор ако је дошло до поделе */
Х1. Нека је ε скуп који садржи све садржаје из чвора Н I његових с-1 сарађујућих чворова са истим оцем.
Х2. Додати р у ε.
Х3. Ако бар један од с-1 сарађујућих чворова са истим оцем није пун, распоредити ε једнако међу с чворова према Хилберт вредностима.
Х4. Ако су свих с сарађујућих чворова са истим оцем пуни: Направити нови чвор НН I распоредити ε једнако међу с+1 чворова према Хилберт вредностима Вратити НН.
Референце[уреди | уреди извор]
- ^ а б I. Камел анд C. Фалоутсос, Он Пацкинг Р-треес, Сецонд Интернатионал АЦМ Цонференце он Информатион анд Кноwледге Манагемент (ЦИКМ), пагес 490-499, Wасхингтон D.C., 1993.
- ^ а б Х. Јагадисх. Линеарно груписање објеката са више атрибута. У Проц. од АЦМ СИГМОД Цонф., стране 332-342, Атлантиц Цитy, Њ, Мај 1990.
- ^ Ј. Гриффитхс. Ан алгоритхм фор дисплаyинг а цласс оф
спаце-филлинг цурвес, Софтwаре-Працтице анд Еxпериенце. . 16 (5): 403—411. Недостаје или је празан параметар
|титле=(помоћ), Маy 1986. - ^ Т. Биаллy. Спаце-филлинг цурвес. Тхеир генератион анд тхеир апплицатион то бандwидтх
редуцтион. ИЕЕЕ Транс. он Информатион Тхеорy. ИТ . 15 (6): 658—664. Недостаје или је празан параметар
|титле=(помоћ), Новембер 1969. - ^ Бецкманн, Норберт; Криегел, Ханс-Петер; Сцхнеидер, Ралф; Сеегер, Бернхард (1990). „Тхе Р*-трее: Ан еффициент анд робуст аццесс метход фор поинтс анд рецтанглес”. Процеедингс оф тхе 1990 АЦМ СИГМОД интернатионал цонференце он Манагемент оф дата. стр. 322–331. ИСБН 0897913655. С2ЦИД 11567855. дои:10.1145/93597.98741.
Референце[уреди | уреди извор]
- I. Камел анд C. Фалоутсос. Параллел Р-Треес. Ин Проц. оф АЦМ СИГМОД Цонф., пагес 195-204 Сан Диего, ЦА, Јуне 1992. Алсо аваилабле ас Тецх. Репорт УМИАЦС ТР 92-1, ЦС-ТР-2820.
- I. Камел анд C. Фалоутсос. Хилберт Р-трее: Ан импровед Р-трее усинг фрацталс. Ин Проц. оф ВЛДБ Цонф., пагес 500-509, Сантиаго, Цхиле, Септембер 1994. Алсо аваилабле ас Тецх_ Репорт УМИАЦС ТР 93-12.1 ЦС-ТР-3032.1.
- Н. Коудас, C. Фалоутсос анд I. Камел. Децлустеринг Спатиал Датабасес он а Мулти-Цомпутер Арцхитецтуре, Интернатионал Цонференце он Еxтендинг Датабасе Тецхнологy (ЕДБТ), пагес 592-614, 1996.
- Н. Роуссопоулос анд D. Леифкер. Дирецт спатиал сеарцх он пицториал датабасес усинг Пацкед Р-треес. Ин Проц. оф АЦМ СИГМОД, пагес 17-31, Аустин, ТX, Маy 1985.
- M. Сцхроедер. Фрацталс, Цхаос, Поwер Лаwс: Минутес Фром ан Инфините Парадисе. W.Х. Фрееман анд Цомпанy, НY, 1991.
- Т. Селлис, Н. Роуссопоулос, анд C. Фалоутсос. Тхе Р+-Трее: а дyнамиц индеx фор мулти-дименсионал објецтс. Ин Проц. 13тх Интернатионал Цонференце он ВЛДБ, пагес 507-518, Енгланд, Септембер 1987.