K-D-B-strom - K-D-B-tree - Wikipedia

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Dubna 2014)

v počítačová věda, a K-D-B-strom (k-dimenzionální B-strom ) je stromová datová struktura pro další dělení a k-rozměrný vyhledávací prostor. Cílem K-D-B-strom je poskytnout vyváženou účinnost vyhledávání k-d strom, zatímco poskytuje blokově orientované úložiště B-stromu pro optimalizaci přístupů do externí paměti.^[1]

Neformální popis

Stejně jako k-d strom, strom K-D-B organizuje body k-dimenzionální prostor, užitečný pro úkoly, jako je vyhledávání rozsahů a vícerozměrné databázové dotazy. Stromy K-D-B rozdělují prostor na dva podprostory porovnáním prvků v jedné doméně. Použitím 2-D-B-stromu (2-rozměrného K-D-B-stromu) jako příkladu je prostor rozdělen stejným způsobem jako k-d strom: pomocí bodu pouze v jedné z domén nebo v tomto případě os, jsou všechny ostatní hodnoty buď menší než nebo větší než aktuální hodnota a spadají nalevo a napravo od dělící roviny.

Na rozdíl od a k-d strom, každý poloprostor není jeho vlastní uzel. Místo toho, jako v B-stromu, jsou uzly v K-D-B-stromu ukládány jako stránky a strom ukládá ukazatel na kořenovou stránku.

Struktura

Základní struktura stromu K-D-B.

Strom K-D-B obsahuje dva typy stránek:

• Stránky regionů: Sbírka (region, dítě) páry obsahující popis ohraničující oblasti spolu s ukazatelem na podřízenou stránku odpovídající dané oblasti.
• Bodové stránky: Sbírka (bod, umístění) páry. V případě databází umístění může ukazovat na index záznamu databáze, zatímco pro body v k-dimenzionální prostor, může být viděn jako souřadnice bodu v tomto prostoru.

K přetečení stránky dochází při vložení prvku do stromu K-D-B, což má za následek, že velikost uzlu překročí jeho optimální velikost. Jelikož účelem stromu K-D-B je optimalizovat přístup k externí paměti, jako jsou přístupy z pevného disku, považuje se stránka za přetečenou nebo přeplněnou, pokud velikost uzlu přesáhne velikost stránky externí paměti.

V průběhu operací vkládání / mazání udržuje strom K-D-B určitou sadu vlastností:

• Graf je vícecestný strom. Stránky regionů vždy odkazují na podřízené stránky a nemohou být prázdné. Bodové stránky jsou listové uzly stromu.
• Stejně jako B-strom je délka cesty k listím stromu pro všechny dotazy stejná.
• Regiony, které tvoří stránku regionu, jsou nesouvislé.
• Pokud je kořenem stránka oblasti, sjednocení jejích oblastí je celý vyhledávací prostor.
• Když dítě a (region, dítě) pair in a region page is also a region page, the union of all the regions in the child is kraj.
• Naopak v případě výše, pokud dítě je bodová stránka, všechny body v dítě musí být obsažen v kraj.

Operace na stromu K-D-B

Dotazy

Dotazy na stromě K-D-B jsou vyhledávání rozsahu v intervalech ve všech doménách nebo osách ve stromu. Tato kolekce intervalů se nazývá oblast dotazu. v k-prostor, oblast dotazu lze vizualizovat jako ohraničující svazek kolem nějakého podprostoru v celém k-rozměrný vyhledávací prostor. Dotaz může spadat do jedné ze tří kategorií:

• Některé intervaly pokrývají celou doménu nebo osu, takže dotaz a částečný rozsah dotaz.
• Některé intervaly jsou body, jiné plné domény, takže dotaz je a částečná shoda dotaz.
• Intervaly jsou všechny body, takže objem ohraničení je také jen bod. Tohle je přesná shoda dotaz.

Algoritmus

1. Pokud vykořenit stromu je null, ukončit, jinak nechat strana být vykořenit.
2. Li strana je bodová stránka, vraťte každou směřovat v (bod, umístění) pár, který leží uvnitř oblast dotazu.
3. V opačném případě, strana je stránka regionu, takže pro všechny (region, dítě) páry kde kraj a oblast dotazu protnout, nastavit strana být dítě a opakování z kroku 2.

Vložení

Protože vložení do stromu K-D-B může vyžadovat rozdělení stránky v případě přetečení stránky, je důležité nejprve definovat operaci rozdělení.

Algoritmus rozdělení

Nejprve se stránka oblasti rozdělí podél nějaké roviny a vytvoří se dvě nové stránky oblastí, levá a pravá stránka. Tyto stránky jsou vyplněny oblastmi ze staré stránky oblasti a stará stránka oblasti je odstraněna. Pak pro každý (kraj, dítě) na původní stránce regionu, pamatuji si dítě je stránka a kraj určuje skutečnou ohraničující oblast:

1. Li kraj leží úplně nalevo od štípací roviny, doplňte (region, dítě) na levou stránku.
2. Li kraj leží úplně napravo od štípací roviny, přidejte (region, dítě) na pravou stránku.
3. V opačném případě:
   1. Rekurzivně rozdělené dítě dělící rovinou, což vede ke stránkám new_left_page a new_right_page
   2. Rozdělit kraj dělící rovinou, což má za následek left_region a right_region
   3. Přidat (left_region, new_left_page) na levou stránku a (right_region, new_right_page) na pravou stránku.

Algoritmus vkládání

Důležitost výběru správné domény rozdělení.

Pomocí dělícího algoritmu vložení nového (bod, umístění) pár lze implementovat následujícím způsobem:

1. Pokud má kořenová stránka hodnotu null, jednoduše z ní udělejte novou bodovou stránku obsahující (bod, umístění)
2. Pokud je dotaz na přesnou shodu zapnut směřovat najít stránku, která bod “by měl být přidán do. Pokud již na stránce existuje, ukončete jej.
3. Přidat (bod, umístění) na stránku. Pokud stránka přetéká, nechte ji strana označte tuto stránku.
4. Nechat old_page být rovno strana. Vyberte nějaký prvek a doménu / osu k definování roviny k rozdělení strana výsledkem jsou dvě stránky, které také nebudou mít za následek přeplnění jedné ze stránek přidáním nového bodu. Rozdělit strana letadlem vytvořit dvě nové stránky, new_left_page a new_right_pagea dva nové regiony left_region a right_region.
5. Li strana byla kořenová stránka, přejděte ke kroku 6. Jinak strana se stane rodičem strana. Nahradit (region, old_page) v strana s (left_region, new_left_page) a (right_region, new_right_page). Li strana přetečení, opakujte krok 4, jinak ukončete.
6. Nechat left_region být celým vyhledávacím prostorem nalevo od štípací roviny a right_region být vyhledávacím prostorem napravo vyplývajícím z rozdělení v kroku 4. Nastavte kořenovou stránku jako stránku obsahující regiony left_region a right_region.

Je důležité pečovat o doménu a prvek zvolený k rozdělení strana tím, že je žádoucí pokusit se vyrovnat počet bodů na obou stranách dělicí roviny. V některých případech může mít špatná volba rozdělení domény za následek nežádoucí rozdělení. Je také možné, že stránku nelze rozdělit podle určité domény.

Vymazání

Odstranění ze stromu K-D-B je neuvěřitelně jednoduché, pokud na využití úložiště nejsou kladeny žádné minimální požadavky. Pomocí dotazu na přesnou shodu najdete a (bod, umístění) pár, jednoduše odstraníme záznam ze stromu, pokud existuje.

Algoritmus reorganizace

Vzhledem k tomu, že smazání může vést ke stránkám, které obsahují velmi málo dat, může být nutné reorganizovat strom K-D-B, aby splňoval některá minimální kritéria využití úložiště. Algoritmus reorganizace, který se má použít, když stránka obsahuje příliš málo dat, je následující:

1. Nechat strana být rodičem P, obsahující (region, P).
2. Najděte regiony v strana tak, že regiony sousedí a jejichž spojení tvoří obdélníkovou oblast. Tyto oblasti jsou považovány za „spojitelné“. Nechat R označují množinu těchto regionů.
3. Sloučit sadu R do jedné stránky S, a pokud S je přeplněná, opakovaně rozdělená, dokud žádná z výsledných stránek nebude přeplněná.
4. Vyměňte sadu R regionů v strana s výslednými stránkami z rozdělení S.

Související práce

Jako v a k-d strom, aktualizace ve stromu K-D-B mohou mít za následek požadavek rekurzivního rozdělení několika uzlů. To je neuvěřitelně neúčinné a může to mít za následek neoptimální využití paměti, protože to může mít za následek mnoho téměř prázdných listů. Lomet a Salzberg navrhli strukturu nazvanou hB-strom (děravý cihlový strom) ke zlepšení výkonu stromů K-D-B omezením rozdělení, ke kterým dochází po vložení, pouze na jednu cestu od kořene k listu. Toho bylo dosaženo ukládáním regionů nejen jako obdélníky, ale jako obdélníky s obdélníkem odstraněným ze středu.^[2]

BKD strom

V poslední době byl strom Bkd navržen jako prostředek k poskytování rychlých dotazů a téměř 100% využití prostoru statického stromu K-D-B. Místo udržování jediného stromu a opětovného vyvážení sada ${ displaystyle log _ {2} (N / M)}$ Stromy K-D-B jsou udržovány a přestavovány v pravidelných intervalech.^[3] V tomto případě, ${ displaystyle M}$ je velikost vyrovnávací paměti paměti v počtu bodů.

Reference