Tato kapitola prezentuje první plně dynamickou a reaktivní datovou strukturu pro efektivní ukládání (a zpětné načítání) geometrických objektů na vícenásobných úrovních detailů. Geometrické výběry mohou být umístěny mezi nově vloženými objekty a i mezi smazanými objekty. Detailní úrovně jsou blízce spojeny s technikami kartografické mapové generalizace. Navrhovaná datová struktura podporuje následující generalizační techniky: zjednodušení, seskupení, symbolizaci a výběr. Obrázek 15 ilustruje generalizační proces na ukázce stejné části mapy při měřítku 1:25 000 a zvětšené mapy 1:50 000.
![Generalizační proces na mapě. [1]](resources/15_Map_generalization.png)
Jádro reaktivní datové struktury je reaktivní strom, geometrická indexovaná struktura, která rovněž dbá na výběrovou část generalizace. Ostatní aspekty generalizačního procesu jsou podporovány uvedením doprovodných struktur, například BLG-stromu. Navrhované struktury tvoří důležitý krok ve směru vývoje bezešvé a bezměřítkové databáze.
Dvě geometrické datové struktury, jež mají některé, byť omezené, prostředky pro mnohonásobné detailní úrovně jsou strom polí a reaktivní BSP-strom. Tyto struktury ale nejsou plně dynamické. Prvním pravidlem pro reaktivní strom je, že důležité objekty musí být uchovány ve vyšších úrovních stromu. Toto pravidlo vzniklo spolu s vývojem reaktivního BSP-stromu.
Vlastnosti reaktivního stromu budou popsány v následující podkapitole spolu s přímým vyhledávacím algoritmem (streightforward Search algorythm). Dále v této kapitole budou uvedeny algoritmy vkládání a mazání, podpora pro generalizační techniky zjednodušení a nakonec bude prezentována alternativní varianta reaktivního stromu. Ta nebude založena na pravidle uvedeném výše.
V této části se budeme se zabývat otázkou nutnosti hodnot důležitosti (importance values) asociovaných k objektům.
Jednoduše řečněno, generalizace je proces vytváření map malého měřítka z map velkého měřítka. (Mapy velkého měřítka mají mnohem více detailů.) Jedním hlediskem tohoto procesu je odstranění nedůležitých a často i zbytečných malých objektů. Toto odstraňování lze opakovat i vícekrát, pokaždé pro mapu s menším měřítkem a s méně objekty v dané oblasti. Každý objekt má přidělenou logickou hodnotu důležitosti, přirozené číslo, v souladu s nejmenším měřítkem, ve kterém je objekt ještě přítomný. Méně důležité objekty dostanou nízké hodnoty, důležitější objekty dostanou větší hodnoty.
Které objekty jsou důležité, záleží na aplikaci. Ve většině aplikací je přirozená hierarchie již přítomna. V případě mapy silnice by to byly například dálnice, hlavní čtyřproudové silnice, obousměrné silnice a nezpevněné cesty. Dalším příkladem mohou být jezera, řeky a kanály, klasifikované do několika skupin podle důležitosti. Počet úrovní je běžně mezi pěti a deseti, což závisí na velikosti a typu geografických souborů dat. V rozumné distribuci dat je počet důležitých objektů o jeden nebo dva řády větší než počet objektů v další vyšší důležitostní úrovni. [1] Jedná se o takzvanou hierarchickou distribuci.
Několik existujících geometrických datových struktur je vhodných pro zahrnutí objektů s odlišnými hodnotami důležitosti, například R-strom, sférický strom a dynamický KD2B strom. [1] Reaktivní strom probíraný v této kapitole bude založen na R-stromu, protože R-strom je nejlepší známou strukturou. Ačkoliv v případě vhodnosti necitlivosti k orientaci by mohla být použita jiná ze zmíněných struktur. Reaktivní strom je mnohacestný strom, ve kterém, každý uzel běžně obsahuje množství položek. Rozlišujeme dva typy položek: objektové položky (object-entries) a stromové položky (tree-entries). Oproti R stromu zde mohou vnitřní uzly obsahovat obě. Koncové uzly (listy) reaktivního stromu obsahují pouze objektové položky.
Objektová položka má tvar (MBR, hodnota důležitosti, identifikátor objektu), kde MBR je minimální ohraničující obdélník, hodnota důležitosti je přirozené číslo značící důležitost a identifikátor objektu obsahuje odkaz k objektu. Dvojdimenzionální MBR zabere 4 čísla (typu floating-point), například 16 bajtů. Hodnota důležitosti zabere 1 bajt, který vystačí pro 256 úrovní důležitosti. Identifikátor objektu zabere 4 bajty s možností odkázání se na 4 000 000 000 objektů. Takže v realistické implementaci reaktivního stromu je velikost objektové položky 21 bajtů.
Stromová položka má formu (MBR, hodnota důležitosti, ukazatel na potomka) , kde ukazatel na potomka obsahuje odkaz na podstrom. V tomto případě MBR je minimální ohraničující obdélník celého podstromu a hodnota důležitosti je důležitostí uzlu potomka zvýšená o jednu. Důležitost uzlu je definovaná jako důležitost jeho položek. Velikost stromové položky je stejná jako velikost objektové položky. Pokud je 1 bit v identifikátoru objektu/ukazateli na potomka použit k rozlišení mezi dvěma položkovými typy, pak mezi nimi není v implementaci žádný fyzický rozdíl a je stále možné odkázat se na 2 000 000 000 objektů, což je pro praktickou aplikaci dostačující. Každý uzel reaktivního stromu odpovídá jedné diskové stránce. Právě tak jako v R-stromu, M indikuje maximální počet položek, které se vejdou do uzlu a m ≤ [M/2] a je minimálním počtem položek. Za předpokladu, že velikost stánky je 1024, pak M je ve skutečné implementaci 48.
V této části budeme prezentovat vlastnosti reaktivního stromu. Fakt, že prázdný strom uspokojí tyto vlastnosti, a to že algoritmy vkládání a mazání je nezničí, zaručí existence reaktivního stromu. Reaktivní strom splňuje následující vlastnosti:
Pro každou objektovou položku (MBR, hodnota důležitosti, identifikátor objektu), MBR je nejmenší osově souměrný obdélník, který geometricky obsahuje reprezentovaný objekt důležitosti (hodnotu důležitosti).
Pro každou stromovou položku (MBR, hodnota důležitosti, ukazatel na potomka), MBR je nejmenší osově souměrný obdélník, který geometricky obsahuje všechny obdélníky v uzlu potomka a hodnota důležitosti je důležitost uzlu potomka zvětšeného o 1.
Všechny položky obsažené v uzlech na stejné úrovni jsou si, co se důležitosti týče, rovny a položky větší důležitosti jsou uchovávány ve vyšších úrovních.
Každý uzel obsahuje m až M objektových položek a/nebo stromových položek. Výjimkou je případ, kdy uzel nemá bratry a jedná se o pseudo-kořen.
Kořen obsahuje minimálně 2 položky, pokud se tedy nejedná o list.
![Prostředí a obdélníky reaktivního stromu. [1]](resources/16_Reactive_Tree_Scene_Rectangles.png)
Je tedy zřejmé, že nejméně důležité objektové položky celého datového souboru jsou vždy obsaženy v listech uzlů na stejné úrovni. Oproti R-stromu se listy mohou vyskytnout i ve vyšších úrovních. To je dáno komplikovanějším vyvažovacím kritériem, které je požadováno mnohonásobnými úrovněmi důležitosti. Dále tyto vlastnosti naznačují, že na vnitřním uzlu, který obsahuje objektové a stromové položky, je důležitost obou těchto položek stejná. Obrázek 16 ukazuje případ s objekty se dvěma úrovněmi důležitosti: objekty důležitosti 1 jsou kresleny bíle a objekty důležitosti dva jsou kresleny šedě. Tento obrázek rovněž ukazuje odpovídající obdélníky použité v reaktivním stromu. Objektové položky v reaktivním stromu jsou zakroužkovány na obrázku 17. Důležitost kořenového uzlu je 3 a důležitost uzlu listu je 1.
![Reaktivní strom. [1]](resources/17_Reactive_Tree.png)
Čím více se v mapě přiblížíme (zoom), tím více úrovní stromu se musí projít. Hrubě řečeno, během mapové generalizace založené na výběru z reaktivního stromu, by se měla vyzkoušet vybrat požadovaná hodnota důležitosti taková, aby byl počet objektů konstantní. (Viz pravidlo konstantní obrazové hustoty informace.) To znamená, že pokud je požadovaná oblast velká, měly by být vybrány pouze důležitější objekty a pokud je požadovaná oblast malá, pak musí být vybrány i méně důležité objekty. Rekurzivní vyhledávací algoritmus slouží k ohlášení všech objektových položek, které mají hodnotu důležitosti imp a jejichž MBR obdélníky překrývají vyhledávací oblast S. Tento algoritmus je volán pokud:
důležitost aktuálního uzlu N < imp (Nejsou žádné kvalifikující záznamy v tomto uzlu ani v jednom z jeho podstromů.)
důležitost aktuálního uzlu N ≥ imp (Ohlásí všechny objektové položky v tomto uzlu, které překrývají S.)
důležitost aktuálního uzlu N > imp (Rovněž se volá vyhledávací algoritmus pro podstromy, které odpovídají stromovým položkám, které překrývají S.)
Vyhledávací algoritmus je jednoduchou částí implementace reaktivního stromu. Tu těžší část tvoří algoritmy vkládání a mazání, které musí zachovávat vlastnosti reaktivního stromu. V implementaci reaktivního stromu prezentovaného v této práci, existuje pro každou hodnotu důležitosti právě jedna úroveň. Hodnoty jsou v rozsahu od min_imp do max_imp, kde min_imp a max_imp odpovídají nejméně a nejvíce důležitému objektu. Pokud je to nutné, tak může být ještě jedna nebo více úrovní stromu nad touto úrovní. Úrovně důležitosti pak budou odpovídat hodnotám max_imp + 1 a vyšším. Uzly horní úrovně obsahují pouze stromové položky. Předpokládejme, že tree_imp ≥ max_imp a tree_imp je důležitost kořene reaktivního stromu. Pak výška stromu je tree_imp + 1 – min_imp. Hodnoty min_imp a tree_imp jsou uchovány v globálních proměnných. (V algoritmu popsaném dále jsou často ignorovány záležitosti udržování správných hodnot v těchto proměnných. Vzhledem k přímému vztahu mezi důležitostí (importance) a úrovní uzlu (level of a node) v reaktivním stromu této implementace může být imp_hodnota v položkách objektů i v položkách stromu vynechána.)
Algoritmus vložení (insert) popsaný níže se nevypořádá s následujícími speciálními případy: prázdný strom, vklad položky s důležitostí větší než je tree_imp. Řešení pro oba případy spočívá v implementování globální proměnné tree_imp a jejím nastavení na vhodnou hodnotu. Algoritmus vkládá nové položky E o důležitosti E_imp v reaktivním stromu takto:
Sestupuje stromem tak, že rekurzivně vybírá nejlepší položky (best tree-entry) stromu a snaží se nalézt uzel N. To se děje dokud není dosažen uzel důležitosti E_imp nebo jeho list. Nejlepší stromová položka je definovaná jako položka, která požaduje nejmenší zvětšení svého MBR k pokrytí E. Algoritmus přizpůsobuje MBR vybraných položek stromu zatímco sestupuje od kořene k uzlu N.
Ve speciálních případech, kde uzel N je list a důležitost N_imp je větší než E_imp, vytvoří lineární cestu uzlů (s délkou N_imp – E_imp) od uzlu N k nové položce. Každý uzel v této cestě pak obsahuje pouze jednu položku. To je dovoleno, protože všechny uzly jsou pseudo kořeny (pseudo-roots).
Vloží cestu k nové položce E v uzlu N. Jestliže se vyskytne přetečení (overflow), rozdělí uzel na uzly N a N’ a aktualizuje rodiče. V případě, že i rodič přeteče, dojde k jeho dalšímu rozdělení směrem nahoru.
Pokud rozdělení uzlu nahoru způsobí rozdělení kořene, zvýší tree_imp o 1 a vytvoří nový kořen, jehož potomci jsou dva výsledné uzly.
Rozdělení uzlu v bodě 3 je analogové k rozdělení uzlu v R-stromu. Nevýhodou reaktivního stromu je možnost výskytu pseudo kořenů, které v určitém případě mohou požadovat nadměrné využívání paměti.
Existující objekt je smazán aplikací algoritmu delete:
Algoritmus nalezne uzel N, který obsahuje objektovou položku (object-entry), při použití jeho MBR.
Odstraní objektovou položku z uzlu N.
Pokud se vyskytne podtečení (underflow), pak položky nenaplněného uzlu jsou uloženy v dočasné struktuře a teprve potom je uzel N odstraněn. V případě, že i rodič nebude naplněný (under-full), opakuje tento proces. Je možné, že podtečení uzlu pokračuje dokud není dosaženo kořene. V tom případě je hodnota tree_imp snížena.
Přizpůsobí MBR všech stromových položek cestou zpátky od odstraňovaných objektů ke kořeni.
Pokud se vyskytne podtečení, aplikuje se algoritmus vložení a vloží se všechny uložené položky na vhodnou úroveň reaktivního stromu.
Existují 3 typy podtečení v reaktivním stromu: kořen obsahuje pouze 1 stromovou položku a pseudo kořen neobsahuje žádnou položku, nebo jeden z ostatních uzlů obsahuje m–1 položek. Dočasná struktura může obsahovat objektové položky a stromové položky odlišných úrovní důležitosti.
Reaktivní strom odráží pouze část z generalizačního procesu, a to výběr (selection). Skutečně reaktivní datová struktura se ale rovněž vypořádává i s ostatními aspekty generalizačního procesu. Zahrneme tedy 3 další aspekty generalizace: zjednodušení (simplification), symbolizaci (symbolization) a seskupení (aggregation). V praxi mohou být velmi dobře implementovány pomocí objektově orientovaného programovacího jazyka, kterým je např. Procol.
![Skládání objektů - velký objekt je složen z několika malých. [1]](resources/18_Object_Composition.png)
Zjednodušení je vhodná technika pro objekty tvořené polygony a polyliniemi. Kromě souřadnic, struktura objektů obsahuje také BLG strom. Procházením BLG stromu s určitou chybou epsilon, získáme dobrou grafickou reprezentaci. BLG-strom je nejvhodnější pro polylinie a polygony definované velkým množstvím bodů. Pro malé množství bodů, může být efektivnější vykonání Douglas-Peuckerova algoritmu za běhu („on the fly“).
Symbolizace mění základní reprezentaci geografického prvku, například polygon je nahrazen polylinií nebo bodem na menším měřítku mapy. Struktura objektu zahrnuje kromě souřadnic polygonu ještě druhou reprezentaci ve formě polylinie nebo bodu. Rozsah měřítka je asociován s každou reprezentací a značí, kde je daná reprezentace platná. Příklad aplikace symbolizační techniky je město zobrazené na mapě malého měřítka jako tečka a na mapě velkého měřítka jako polygon.
Seskupení je poslední generalizační technikou zahrnutou v reaktivní datové struktuře. Jedná se o kombinaci několika malých objektů do jednoho velkého objektu. Z pohledu hierarchického stromu vzhůru nohama jsou velké objekty komponovány z několika malých, viz obrázek 18. Geometrický popis velkého objektu a geometrický popis malých objektů je vždy uchován, protože mezi nimi není jednoduchý vztah. Velký objekt funguje jako obálka kolem objektů malých. Ohraničující obálka kolem malých objektů je obvykle dostatečná „geometrická vyhledávací struktura“ (geometric search structure), protože počet malých objektů je omezen. Ačkoliv, pokud je počet malých objektů (oproti velkým) dosti velký, pak může být využit R-podstrom.
Seskupení je použito, například na mapě administrativních jednotek Holandska viz obrázek 11. Několik měst je seskupeno do velké ekonomicko-geografického oblasti EGR (ekonomic geographic region). Ty jsou seskupeny do uzlových oblastí, které jsou uskupeny do provincií a tak dále.
V této podkapitole je prezentována reaktivní datová struktura, která není založena na pravidlu uchovávání důležitých objektů ve vyšších úrovní stromu. Výhodou alternativního reaktivního stromu (Alternative Reactive-tree) oproti reaktivnímu je, že nepředpokládá distribuci dat s hierarchickým uspořádáním pomocí úrovní důležitosti.
![Trojrozměrné MBR obdélníky alternativního reaktivního stromu. [1]](resources/19_Reactive_Tree_Alternative.png)
Alternativní 2D reaktivní strom je založen na 3D R-stromu. 3D MBR z 2D objektu s důležitostí imp je definován pomocí 2D MBR obdélníku. Jeho třetí rozměr tvoří hodnoty imp a imp + δ, kde δ je kladné reálné číslo, a objekt tak odpovídá bloku s nenulovým obsahem (s výjimkou bodových objektů). Obrázek 19 zobrazuje 3D MBR několika 2D objektů na dvou odlišných úrovních důležitosti. Když bude vybrán velice malý parametr δ, například 0,01, alternativní reaktivní strom se pokusí uskupit objekty, které patří na stejnou úroveň důležitosti. To je kvůli velké dani za zahrnutí objektu s jinou hodnotou důležitosti, zvláště když se zvýší objem 3D MBR obdélníku o faktor alespoň (1 + δ) / δ. Čím větší se stane δ, tím menší daň zaplatíme, a tím spíše se objekty různé důležitosti uskupí. Alternativní reaktivní strom se pak bude chovat více jako 2D R-strom. V každém případě, všechny objekty, jak důležité, tak nedůležité, budou uchovány v uzlech listů na stejné úrovni.
Alternativní reaktivní strom může být zobecněn tak, aby místo hierarchických hodnot důležitosti podporoval objekty s obecnými jmenovkami (general labels). To umožní dotazy jako „Vyberte všechna hlavní města v oblasti R“. Jmenovka hlavních měst je asociována s některými geografickými objekty po jejich vložení do stromu. Geografické objekty mohou být asociovány i k více jmenovkám. V implementaci jmenovka odpovídá numerické hodnotě. Výběrem jistých hodnot pro tyto jmenovky a pro δ můžeme využít určitou souvislost mezi nimi. [1]
Popsali jsme první plně dynamickou a reaktivní datovou strukturu a prezentovali jsme ji ve 2D. Jsou ale rovněž možné i její 3D a více dimenzionální varianty. Reaktivní strom a alternativní reaktivní strom byly založeny na R-stromu. Analogicky k R-stromu, je rovněž možné vytvořit reaktivní strom založený na sférickém stromu.
K testování reaktivních datových struktur byly v [1] používány velké datové soubory, například mapa administrativních jednotek Nizozemí. Testy ukázaly výhodu výběru (selection) založeného na úrovních důležitosti (importance levels) a geometrické pozici (geometric position). Bylo možné zobrazit celé oblasti mapy s interaktivní rychlostí, oproti situaci, kdy normální R-strom zobrazil příliš mnoho zbytečných detailů. V současnosti jsou implementovány další struktury podporující zjednodušování, symbolizaci a seskupení.
Generalizační techniky zdůraznění (exaggeration) a přemístění (displacement) zde nebyly probírány. Zdůraznění bude zřejmě jednoduché, protože se jedná pouze o zvětšení grafické reprezentace jednoho objektu. Zvětšení lineárních rysů by ale mohlo způsobit překrytí jiných, a tak by se musely přemístit (displace). K vyvinutí elegantního řešení je nutný další výzkum.
Dále by měly být vyvinuty nové reaktivní stromy, které budou schopny vypořádat se efektivně s nehierarchicky uspořádaným množstvím objektů pomocí úrovní důležitosti, a měly by se držet pravidla, aby důležité objekty byly uloženy ve vyšších vrstvách stromu. To může být uskutečněno například změnou vlastností v tom smyslu, že jedna úroveň stromu bude obsahovat vícenásobné úrovně důležitosti, ale není ještě jasné, jak by měl být modifikován algoritmus vložení a mazání, což je předmětem dalšího výzkumu. [1]