Hilbertův R-strom , varianta R-stromu , je indexování vícerozměrných objektů, jako jsou čáry, dvourozměrné oblasti, trojrozměrné objekty nebo parametrizované objekty vyšších rozměrů. Lze je chápat jako rozšíření B+-stromů na vícerozměrné objekty.
Výkon R-stromů závisí na kvalitě algoritmu, který seskupuje data do obdélníků. R-stromy používají křivky vyplňující prostor , konkrétněji Hilbertovy křivky , k lineárnímu uspořádání objektů do obdélníků.
Existují dva typy Hilbertových R-stromů, jeden pro statická data a jeden pro dynamická data. V obou případech se k získání lepšího uspořádání vícerozměrných objektů používají Hilbertovy křivky vyplňující prostor. Toto uspořádání je "dobré" v tom smyslu, že by mělo seskupit "podobná" data do obdélníků, čímž se minimalizuje plocha a obvod těchto minimálních ohraničujících obdélníků (MBR) Zabalené Hilbertovy R-stromy jsou vhodné pro statická data, která se aktualizují velmi zřídka nebo vůbec.
Dynamické Hilbert R-Stromy jsou vhodné pro měnitelná data, kde vkládání, mazání nebo aktualizace probíhá v reálném čase. Dynamické Hilbert R-stromy navíc využívají flexibilní odložený štípací mechanismus, který zlepšuje manipulaci s prostorem. Každý uzel má dobře definovanou sadu sourozeneckých uzlů (s jedním rodičem). Úpravou politiky rozdělení pomocí Hilbertových R-stromů můžete získat stupeň zpracování prostoru na požadované úrovni. Hilbertovy R-stromy třídí obdélníky podle Hilbertových vzdáleností středů obdélníků (MBR). (Hilbertova vzdálenost bodu je rovna délce Hilbertovy křivky od začátku křivky k bodu.). Naproti tomu jiné varianty R-stromů nemají žádné mechanismy pro ovládání manipulace s prostorem.
Přestože následující příklad odkazuje na statické prostředí, vysvětluje intuitivní principy, které stojí za budováním dobrých R-stromů. Tyto principy platí pro statická i dynamická data. Roussopoulos a Leifker navrhli metodu pro konstrukci sbaleného R-stromu, který dosahuje téměř 100% zpracování. Cílem je seřadit data podle souřadnic x nebo y z jednoho rohu obdélníku. Řazení podle kteréhokoli ze čtyř rohů poskytuje podobné výsledky. V tomto článku jsou body a obdélníky seřazeny vzhledem k souřadnici x levého dolního rohu obdélníku a metoda Roussopoulose a Leifkera se bude nazývat „x-packed R-tree“. Metoda prochází setříděným seznamem obdélníků. Postupné obdélníky jsou přiřazeny stejnému listu R-stromu, dokud není uzel plný. Poté se vytvoří nový list a pokračuje procházení setříděného seznamu. Uzly výsledného R-stromu tedy budou kompletně zabaleny, snad s výjimkou posledního uzlu na každé úrovni. Prostorové zpracování se tedy blíží 100 %. Vyšší úrovně stromu jsou vytvořeny podobně.
Obrázek 1 ukazuje problémy x-packed R-stromů. Obrázek (vpravo) ukazuje uzly R-stromu získané touto metodou pro body zobrazené vlevo. Skutečnost, že výsledné nadřazené uzly pokrývají malou oblast, vysvětluje rychlou degradaci požadavků na body. Velký obvod obdélníků však vysvětluje, proč se dotazy na oblasti rychle zhoršují. To je v souladu s analytickými vzorci pro výkon R-stromů [1] . Je intuitivně jasné, že balicí algoritmus by měl přiřadit blízké body stejnému uzlu. Ignorování y-ové souřadnice pomocí "x-sbaleného R-stromu" porušuje toto základní pravidlo.
Obrázek 1: [Vlevo] 200 rovnoměrně rozmístěných bodů. [Vpravo] MBR uzlů generovaných algoritmem " R-tree x-packing " .
Počáteční Hilbertova křivka na mřížce 2x2, označená jako H 1 , je znázorněna na obrázku 2. Pro získání křivky řádu i je každý vrchol hlavní křivky nahrazen křivkou řádu i - 1, otočená a/nebo odražená jako nutné. Obrázek 2 také ukazuje Hilbertovy křivky řádu dva a tři. Protože řád křivky má tendenci k nekonečnu, stejně jako ostatní křivky vyplňující prostor, křivka se mění ve fraktál s fraktálním rozměrem dva [1] [2] . Hilbertovu křivku lze zobecnit do vyšších dimenzí. Algoritmus pro kreslení dvourozměrné křivky daného řádu lze nalézt v Griffiths [3] a Jagadish [2] . Algoritmus pro vyšší dimenze poskytl Bialli [4] .
Křivka vyplňující prostor vytváří lineární uspořádání bodů mřížky. Tuto cestu lze sestavit tak, že začnete od jednoho konce křivky k druhému, přičemž všechny body projdete na konec křivky. Obrázek 2 ukazuje jedno takové uspořádání pro mříž 4x4 (viz křivka H2 ) . Například bod (0,0) na křivce H 2 má vzdálenost 0 a bod (1,1) má vzdálenost 2. Hilbertova vzdálenost obdélníku je podle definice Hilbertova vzdálenost jeho středu.
Obrázek 2: Hilbertovy křivky 1., 2. a 3. řádu
Hilbertova křivka definuje lineární uspořádání datových obdélníků. Při procházení uspořádaným seznamem přiřadíme každou sadu obdélníků k uzlu v R-stromu. Výsledkem je, že mnoho datových obdélníků na stejném uzlu bude blízko sebe v lineárním pořadí a s největší pravděpodobností blízko v přirozeném prostoru. Výsledné uzly R-stromu tedy budou mít malou plochu. Obrázek 2 ukazuje důvody, proč metody založené na Hilbertových křivkách vedou k dobré výkonnosti. Data se skládají z bodů (stejně jako na obrázku 1). Seskupením bodů podle jejich Hilbertových vzdáleností jsou MBR výsledných uzlů R-stromu obvykle malé, téměř čtvercové obdélníky. To znamená, že uzly mají pravděpodobně malé oblasti a obvody. Malé hodnoty oblasti vedou k dobrému výkonu dotazů na body. Malé oblasti a malé obvody poskytují dobrý výkon pro velké dotazy.
(Algoritmus balení obdélníku R-tree)
Krok 1. Vypočítejte Hilbertovu vzdálenost pro každý datový obdélník
Krok 2. Seřaďte obdélníky vzestupně podle Hilbertovy vzdálenosti
Krok 3. /* Vytvořte listy (úroveň l = 0) */
Krok 4. /* Vytvořte uzly na úrovni ( l + 1) */
To předpokládá, že data jsou statická nebo se mění jen zřídka. Algoritmus je jednoduchý heuristický algoritmus pro konstrukci R-stromu se 100% manipulací s prostorem a má také dobrou dobu odezvy.
Výkon R-stromů závisí na kvalitě algoritmu pro shlukování dat do obdélníků v uzlu. Hilbertovy R-stromy používají křivky vyplňující prostor s lineárním uspořádáním obdélníků. Hilbertova vzdálenost obdélníku je podle definice rovna vzdálenosti jeho středu.
Hilbertův R-strom má následující strukturu. List obsahuje maximálně C l prvků, každý ve tvaru (R, obj _id), kde C l je kapacita listu, R je MBR reálného objektu (x low , x high , y low , y high ) a obj-id je ukazatel na záznam popisu objektu. Hlavní rozdíl mezi Hilbertovým R-stromem a R*-stromem [5] je v tom, že nelistové uzly obsahují informace LHV (největší Hilbertova hodnota). Nelistové uzly v R-stromu tedy obsahují nejvýše Cn prvků tvaru (R, ptr, LHV), kde C n je kapacita nelistového uzlu, R je MBR, který zahrnuje všechny potomky tento uzel, ptr je ukazatel na potomka a LHV je největší Hilbertova vzdálenost dat v ohraničujícím rámečku R. Všimněte si, že protože nelistový uzel má jako LHV Hilbertovu vzdálenost jednoho ze svých potomků, není zde žádná další náklady na výpočet Hilbertových vzdáleností MBR nelistových uzlů. Obrázek 3 znázorňuje některé krabice uspořádané do Hilbertova R-stromu. Hilbertovy vzdálenosti středů jsou čísla kolem symbolů „x“ (zobrazeno pouze pro nadřazený uzel „II“). Hodnoty LHV jsou uvedeny v [závorkách]. Obrázek 4 ukazuje, jak je strom na obrázku 3 uložen na disku. Podrobněji je zobrazen obsah nadřazeného uzlu "II". Libovolný datový obdélník uzlu "I" má hodnotu v ≤33. Podobně jakýkoli obdélník uzlu "II" má Hilbertovu vzdálenost větší než 33 a menší než 107 a tak dále.
Obrázek 3: Datové schránky uspořádané do Hilbertova R-stromu (Hilbertovy vzdálenosti a hodnoty LHV jsou v závorkách)
Jednoduchý R-strom rozbije uzel při přetečení a vytvoří dva uzly. Tato zásada se nazývá zásada rozdělení 1:2. Můžete odložit rozdělení a převést dva uzly na tři. Všimněte si, že tato zásada je podobná zásadě dělení B*-stromu. Tato metoda se nazývá 2-to-3 split policy. V obecném případě můžeme mluvit o rozdělovací politice s-in-(s+1), kde s je pořadí rozdělovací politiky. Aby bylo možné implementovat politiku dělení řádů s, přeplněný uzel se pokusí umístit některé uzly do jednoho ze svých příbuzných s - 1 (uzlů na stejné úrovni). Pokud jsou všechny vyplněny, musíte rozdělit s-na-(s+1). Tyto příbuzné s -1 se nazývají spolupracující uzly. Algoritmy pro vyhledávání, vkládání a přetečení jsou podrobně popsány níže.
Algoritmus hledání je podobný algoritmům v jiných variantách R-stromů. Algoritmus počínaje kořenem sestupuje ze stromu a kontroluje všechny oblouky, které protínají vyhledávací obdélník. Na listu algoritmus zahrnuje všechny nalezené prvky v okně dotazu w.
Procedura Najít (uzel Kořen, obdélník w):
S1. Hledání uzlů, které nejsou listy:
S2. Hledání listů:
Obrázek 4: Struktura souboru Hilbert R-tree
Pro vložení nového obdélníku r do Hilbertova R-stromu se jako klíč použije Hilbertova vzdálenost h středu nového obdélníku. Na každé úrovni je mezi všemi prvky úrovně vybrán uzel s minimální hodnotou LHV větší než h. Je-li dosaženo listu, vloží se do něj obdélník r ve správném pořadí podle hodnoty h. Po vložení nového obdélníku do listu N se spustí procedura Tree Reconciliation pro změnu hodnot MBR a LHV na uzlech vyšší úrovně.
Procedure Insert(Kořenový uzel, obdélník r) : /* Vloží nový obdélník r do Hilbertova R-stromu.
h je Hilbertova vzdálenost obdélníku*/
I1. Nalezení správného listu:
I2. Vložte r do listu L:
I3. Propagace změn:
Tvoříme množinu S obsahující L, kooperativní uzly a nový list (pokud existuje) Spustíme proceduru Matching the Tree (S).I4. Zvýšení výšky stromu:
Pokud šíření změn způsobí rozdělení kořenů, vytvořte nový kořen, jehož potomky jsou dva uzly vzniklé rozdělením kořene.Procedure FindSheet(obdélník r, celé číslo h) :
/* Vrátí list, do kterého se má umístit nový obdélník r. */
C1. Inicializace:
C2. Kontrola listu:
Je-li N list, vraťte N.C3. Výběr podstromu:
Pokud N není list, vyberte prvek (R, ptr, LHV) s minimálním LHV větším než h.C4. Jdeme dolů, dokud nedosáhneme listu:
Nastavte N na uzel, na který ukazuje ptr a opakujte proces od bodu C2.Odsouhlasení stromu procedur (množina S) :
/* S je množina uzlů obsahujících uzly, které mají být změněny,
jejich spolupracující uzly (pokud došlo k přetečení)
a vytvořený uzel NN (pokud bylo provedeno rozdělení uzlů).
Procedura stoupá od listu ke kořenu a mění MBR a LHV uzlů pokrývajících uzly v S.
Procedura zpracovává rozdělení uzlů (pokud existují) */
A1. Pokud dosáhneme kořene, zastavíme se.
A2. Zpracování rozdělení uzlů:
A3. Změňte hodnoty MBR a LHV na nadřazené úrovni:
Nechť P je množina nadřazených uzlů pro uzly v S. Změníme odpovídající hodnoty MBR a LHV v P uzlech.A4. Přechod na další úroveň:
S se stává množinou rodičovských uzlů P, NN = PP, pokud byl Np rozdělen. přejděte na A1.V Hilbertově R-stromu není potřeba znovu vkládat visící uzly, dokud nezmizí nadřazený uzel. Místo toho jsou klíče, které lze převzít ze základních uzlů, sloučeny s prvky stejné úrovně. To je možné, protože uzly mají jasné řazení (podle LHV). Naproti tomu u R-stromů takový koncept neexistuje. Všimněte si, že operace odstranění vyžaduje s spolupracujících uzlů, zatímco operace vložení vyžaduje s - 1 prvků.
Postup Smazat(r) :
D1. Hledání listu:
D2. Odebrat r:
D3. Pokud je L prázdné
D4. Měníme hodnoty MBR a LHV na nadřazených úrovních.
Postup manipulace s přetečením v Hilbertově R-stromu zpracovává přetečení uzlů buď přesunutím některých prvků do jednoho z kooperačních uzlů s - 1, nebo rozdělením s uzlů na s + 1 uzlů.
Procedure Overflow Handling(uzel N, obdélník r) :
/* vrátí nový uzel, pokud došlo k rozdělení. */
H1. Nechť ε je množina obsahující všechny prvky z N
H2. Přidáme r k ε.
H3. Pokud není vyplněn alespoň jeden ze spolupracujících uzlů s - 1,
H4. Pokud jsou všechny kooperativní uzly vyplněny,
vytvořte uzel NN a rovnoměrně rozmístěte ε nad s + 1 uzly podle Hilbertových vzdáleností návrat N.N.Strom (datová struktura) | |
---|---|
Binární stromy | |
Samovyrovnávací binární stromy |
|
B-stromy |
|
předponové stromy |
|
Binární dělení prostoru | |
Nebinární stromy |
|
Rozbití prostoru |
|
Jiné stromy |
|
Algoritmy |
|
Datové struktury | |
---|---|
Seznamy | |
Stromy | |
Počítání | |
jiný |