R-strom (datová struktura)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. září 2015; kontroly vyžadují 23 úprav .
R-strom
Typ Vícerozměrný strom Binární vyhledávací strom
Rok vynálezu 1984
Autor Antonín Guttman
Složitost v O-symbolech
Průměrný Při nejhorším
Vyhledávání O( log M n ) O( n )
 Mediální soubory na Wikimedia Commons

R-tree ( anglicky  R-trees ) je stromová datová struktura ( strom ), navržená v roce 1984 Antoninem Guttmanem . Je podobný B-stromu , ale používá se pro přístup k prostorovým datům, to znamená k indexování vícerozměrných informací , jako jsou geografická data s dvourozměrnými souřadnicemi ( zeměpisná šířka a délka ). Typický dotaz pomocí R-stromů může znít: „Najít všechna muzea v okruhu 2 kilometrů od mé aktuální polohy.“

Tato datová struktura rozděluje vícerozměrný prostor na sadu hierarchicky vnořených a případně se protínajících obdélníků (pro dvourozměrný prostor). V případě trojrozměrného nebo vícerozměrného prostoru se bude jednat o pravoúhlé rovnoběžnostěny ( kvádry ) nebo rovnoběžníky .

Algoritmy vkládání a odebírání používají tyto ohraničovací rámečky, aby zajistily, že "zavřít" objekty jsou umístěny na stejném vrcholu listu. Nový objekt zasáhne zejména vrchol listu, který potřebuje nejmenší rozšíření svého ohraničujícího rámečku. Každý element listového uzlu ukládá dvě datová pole: způsob, jak identifikovat data, která popisují objekt (nebo samotná data) a ohraničující rámeček tohoto objektu.

Podobně vyhledávací algoritmy (např. průnik, zahrnutí, sousedství) používají ohraničující rámečky k rozhodnutí, zda hledat v podřízeném uzlu. Většina vrcholů se tedy během vyhledávání nikdy nedotkne. Stejně jako u B-stromů je tato vlastnost R-stromů činí vhodnými pro databáze , kde lze vertexy podle potřeby vyměňovat na disk .

K rozdělení přetečených vrcholů lze použít různé algoritmy, což vede k rozdělení R-stromů na podtypy: kvadratické a lineární.

Zpočátku R-stromy nezaručovaly dobrý výkon v nejhorším případě , ačkoli fungovaly dobře na skutečných datech. V roce 2004 však byl publikován nový algoritmus , který určuje prioritní R-stromy . Tvrdí se, že tento algoritmus je stejně účinný jako nejúčinnější moderní metody a zároveň je optimální pro nejhorší případ [1] .

Struktura R-stromu

Každý vrchol R-stromu má proměnný počet prvků (ne více než nějaké předem určené maximum). Každý prvek nelistového vrcholu ukládá dvě datová pole: způsob, jak identifikovat podřízený vrchol, a ohraničující rámeček (kvádr), který uzavírá všechny prvky tohoto podřízeného vrcholu. Všechny uložené n-tice jsou uloženy ve stejné hloubkové úrovni, takže strom je dokonale vyvážený. Při navrhování R-stromu musíte nastavit některé konstanty:

Aby algoritmy správně fungovaly, musí být splněna podmínka MinEntries <= MaxEntries / 2. Kořenový uzel může mít od 2 do MaxEntries potomky. Často se volí MinEntries = 2, pak jsou pro kořen splněny stejné podmínky jako pro zbytek vrcholů. Někdy je také rozumné vyhradit si samostatné konstanty pro počet bodů ve vrcholech listů, protože jich často můžete vytvořit více.

Algoritmy

Vložit

Ke konstrukci R-stromu dochází zpravidla opakovaným voláním operace vložení prvku do stromu. Myšlenka vložení je podobná vložení do B-stromu : pokud přidání prvku do dalšího vrcholu vede k přetečení, pak se vrchol rozdělí. Níže je uveden klasický algoritmus vkládání popsaný Antoninem Guttmanem .

Vložit funkci
  • Volá ChooseLeaf pro výběr listu, kam má být prvek přidán. Pokud je vložení provedeno, strom by mohl být rozdělen a rozdělení by mohlo jít až nahoru. V tomto případě ChooseLeaf vrátí dva SplitNodes k vložení do kořenového adresáře
  • Volá funkci AdjustBounds, která rozšíří ohraničovací rámeček kořene na vkládaný bod
  • Zkontroluje, zda ChooseLeaf vrátil nenulové SplitNodes, pak strom poroste o jednu úroveň výše: od tohoto okamžiku je kořenem vrchol, jehož potomky jsou stejné SplitNodes
Funkce ChooseLeaf
  • pokud je vstupem list (rekurzní báze), pak:
    • volá funkci DoInsert, která přímo vloží prvek do stromu a vrátí dva listy, pokud dojde k rozdělení
    • změní ohraničující obdélník vrcholu tak, aby odpovídal vloženému prvku
    • vrátí SplitNodes vrácené DoInsert
  • pokud je vstupem nelistový vrchol:
    • ze všech potomků se vybere ten, jehož hranice vyžadují minimální zvětšení pro vložení daného prvku
    • rekurzivně volá ChooseLeaf na vybrané dítě
    • opravuje ohraničující obdélníky
    • pokud jsou splittedNodes z rekurzivního volání nulové, pak funkci opustíme, jinak:
      • pokud NumEntries < MaxEntries, pak přidejte nový vrchol k potomkům, vyčistěte SplitNodes
      • jinak (když není kam vložit), zřetězíme pole potomků s novým vrcholem a předáme výslednou funkci funkci LinearSplitNodes nebo jiné funkci pro rozdělení vrcholů a vrátíme z ChooseLeaf ty SplitNodes, které nám vrátila použitá funkce rozdělení. .
Funkce LinearSplit

K oddělení vrcholů lze použít různé algoritmy, toto je jeden z nich. Má pouze lineární složitost a snadno se implementuje, i když neprodukuje nejoptimálnější separaci. Praxe však ukazuje, že taková složitost je obvykle dostatečná.

  • pro každou souřadnici pro celou množinu sdílených vrcholů se vypočítá rozdíl mezi maximální spodní hranicí obdélníku na této souřadnici a minimální horní hranicí, poté se tato hodnota normalizuje rozdílem mezi maximálními a minimálními souřadnicemi bodů původní sadu na stavbu celého stromu
  • najít maximum tohoto normalizovaného rozptylu přes všechny souřadnice
  • nastavit jako první potomky pro vrácené vrcholy node1 a node2 ty vrcholy ze vstupního seznamu, na kterých bylo dosaženo maxima, odstranit je ze vstupního seznamu, upravit hranice pro uzel1 a uzel2
  • poté se provede vložení pro zbývající vrcholy:
    • pokud v seznamu zbývá tak málo vrcholů, že pokud jsou všechny přidány do jednoho z výstupních vrcholů, pak bude obsahovat vrcholy MinEntries, pak se k němu přidá zbytek, návrat z funkce
    • pokud jeden z vrcholů již má maximum potomků, pak se zbytek přičte k opačnému, returnu
    • pro další vrchol ze seznamu se porovná, o kolik se má zvětšit ohraničovací rámeček při vložení do každého ze dvou budoucích vrcholů, kde je méně, tam se vloží
Funkce fyzického vkládání DoInsert
  • pokud jsou u vrcholu volná místa, pak se bod vloží tam
  • pokud tam žádná místa nejsou, tak potomci vrcholu se spojí s vloženým bodem a zavolá se funkce LinearSplit nebo jiná dělící funkce, která vrátí dva rozdělené vrcholy, které vrátíme z doInsert
Rozdělení pomocí shlukovacích algoritmů

Někdy se místo R-stromu používá tzv. cR-strom (c znamená clustered ). Základní myšlenkou je, že k oddělení vrcholů nebo bodů se používají shlukovací algoritmy , jako je k-means . Složitost k-means je také lineární, ale ve většině případů dává lepší výsledek než lineární Guttmanův separační algoritmus, na rozdíl od něj nejen minimalizuje celkovou plochu obálek krabic, ale také vzdálenost. mezi nimi a oblastí překrytí. Pro bodové shlukování se používá zvolená metrika původního prostoru, pro vrcholové shlukování lze použít vzdálenost středů jejich obálek rovnoběžnostěnů nebo maximální vzdálenost mezi nimi.

Shlukovací algoritmy neberou v úvahu skutečnost, že počet potomků vrcholu je shora a zdola omezen konstantami algoritmu. Pokud rozdělení clusteru vede k nepřijatelnému výsledku, můžete pro tuto sadu použít klasický algoritmus, protože se to v praxi často nestává.

Zajímavým nápadem je použití shlukování do několika shluků, kde několik může být více než dva. Je však třeba vzít v úvahu, že to ukládá určitá omezení na parametry struktury p-stromu.

Všimněte si, že kromě cR-stromu existuje jeho variační clR-strom založený na metodě shlukování, kde je jako střed použit iterační algoritmus pro řešení „problému umístění“. Algoritmus má kvadratickou výpočetní složitost, ale poskytuje konstrukci kompaktnějších obálek rovnoběžnostěnů ve struktuře vertexových záznamů.

Hledat

Hledání ve stromu je celkem triviální, jen je potřeba počítat s tím, že každý bod v prostoru může být pokrytý více vrcholy.

Odstranění

Tento algoritmus [2] odstraní některé položky E z R-stromu. Algoritmus se skládá z následujících kroků:

  • Vyhledejte uzel obsahující záznam. Voláním funkce hledání FindLeaf najděte list L obsahující záznam E. Pokud záznam není nalezen, zastavte algoritmus.
  • Smazání záznamu. Vymažte záznam E z listu L.
  • Aktualizovat změny. Zavolejte funkci CondenseTree pro položku L.
  • Kontrola kořene stromu. Pokud kořen stromu není listový uzel a zbývá pouze jeden záznam, udělejte tento záznam kořenem stromu.

Funkce FindLeaf

Nechť T je kořen stromu a E je požadovaný záznam.

  • Vyhledávání podstromů. Pokud T není listový uzel, zkontrolujte každý výskyt položky E v každé položce T podle následující podmínky: pokud je položka E zahrnuta v obdélníku položky v T, zavolejte funkci FindLeaf .
  • Vyhledejte záznam v listovém uzlu. Je-li T list, najděte záznam E v tomto listu a pokud jej najdete, vraťte jej.

Funkce CondenseTree

Nechte záznam E vymazat z listu L. Poté je nutné odstranit uzel, který má málo záznamů (méně než MinEntries) a přesunout jeho záznamy. Při pohybu ve stromu v případě potřeby smažte záznamy (podle stejných kritérií). Cestou ke kořenu přepočítejte obdélníky, aby byly co nejmenší. Algoritmus je popsán níže. Tuto funkci lze také implementovat pomocí rekurze.

  • Inicializace. Nechť N = L a Q je množina vzdálených uzlů, zpočátku prázdných.
  • Najít upstream uzel. Pokud je N kořen, přejděte k poslednímu kroku algoritmu (opětovné vkládání záznamů). Jinak nechť P je rodič uzlu N.
  • Vyloučení malých uzlů. Pokud má uzel N méně položek MinEntries, odeberte N z P a přidejte jej do Q.
  • Přepočet obdélníků. Pokud N nebylo odstraněno, přepočítejte jeho obdélník tak, aby obsahoval všechny položky v N.
  • Pohyb po stromě. Nechť N = P. Opakujte druhý krok hledání rodičovského uzlu.
  • Vkládání "osiřelých" záznamů. Musíte znovu vložit záznamy ze sady Q. Pokud je záznam v Q listový uzel, vložte všechny jeho záznamy pomocí algoritmu Insert . Pokud Q není listový uzel, pak musí být vložen tak, aby všechny jeho listové uzly byly na stejné úrovni stromu jako listové uzly samotného stromu (vlastností R-stromu, podle které všechny listové uzly jsou uloženy na stejné úrovni hloubky stromu).

Diskuze o R-stromech

Výhody

  • efektivně ukládat prostorově lokalizované skupiny objektů
  • vyvážený znamená v nejhorším případě rychlé vyhledávání
  • vložení/smazání jednoho bodu nevyžaduje výraznou přestavbu stromu (dynamický index)

Nevýhody

  • citlivé na pořadí přidaných údajů
  • ohraničující rámečky vrcholů se mohou překrývat

Viz také

  • Seznam datových struktur (stromů)

Poznámky

  1. ↑ Prioritní R-strom: Prakticky účinný a v nejhorším případě optimální R-strom , SIGMOD. Archivováno z originálu 6. března 2021. Staženo 12. října 2011.
  2. ↑ Antonín Guttman. [ https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf R-TREES. DYNAMICKÁ INDEXOVÁ STRUKTURA PRO PROSTOROVÉ VYHLEDÁVÁNÍ]  //  ACM. - 1984. Archivováno 24. března 2018.

Odkazy