Hilbertův R-strom

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.

Hlavní myšlenka

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 " .

Hilbertova křivka

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

Sbalené Hilbert R-stromy

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.

Hilbert-Pack Packing Algorithm

(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.

Hilbert dynamické R-stromy

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.

Stromová struktura

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.

Hledat

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:

Začneme hledat každý prvek, jehož MBR spadá do okna dotazu w.

S2. Hledání listů:

Uvádíme všechny prvky, které spadají do okna dotazu w jako kandidáty.

Obrázek 4: Struktura souboru Hilbert R-tree

Vložit

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:

CallSearchList (r, h) a vyberte list L, do kterého chcete zahrnout r.

I2. Vložte r do listu L:

Pokud má L prázdný slot, vložte r do L na vhodné místo dle pořadí Hilbertových vzdáleností a návrat. Pokud je L plné, zavolejte proceduru Handle Overflow (L,r), který vrátí nový list, pokud je potřeba štípání,

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:

Nastavte N jako kořen.

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ů:

Nechť Np je rodič uzlu N. Pokud byl uzel N rozdělen, nechť NN je nový uzel. Vložte NN do Np ve správném pořadí podle jeho Hilbertovy vzdálenosti, pokud je místo. Jinak nazýváme proceduru Overflow Handling (Np , NN ). Pokud byl uzel Np rozdělen, nechť PP je nový uzel.

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.

Odstranění

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:

Hledáme přesný výskyt listu L, který obsahuje r.

D2. Odebrat r:

Odeberte r z uzlu L.

D3. Pokud je L prázdné

přebíráme některé prvky ze spolupracujících uzlů. pokud takové prvky neexistují, přenést s + 1 uzlů do uzlů s, přepočítat přijaté uzly.

D4. Měníme hodnoty MBR a LHV na nadřazených úrovních.

tvoří množinu S obsahující L a jeho kooperativní uzly (pokud dojde k přetečení). zavolejte MatchTree(S).

Ovládání přetečení

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

a jeho s - 1 spolupracujících uzlů.

H2. Přidáme r k ε.
H3. Pokud není vyplněn alespoň jeden ze spolupracujících uzlů s - 1,

distribuovat ε rovnoměrně přes s podle Hilbertových vzdáleností.

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.

Poznámky

  1. ↑ 1 2 Kamel, Faloutsos, 1993 , str. 490-499.
  2. ↑ 1 2 Jagadish, 1990 , str. 332-342.
  3. ↑ Griffiths, 1986 , s. 403-411.
  4. ↑ Bially, 1969 , str. 658-664.
  5. ↑ Beckmann, Kriegel, Schneider, Seeger 1990 , str. 322.

Literatura