12 - Metody indexování bodových a plošných útvarů - typicky obalujících hyperobdélníků - v prostorových DB Flashcards
Index v prostorových db
datová struktura sloužící k akceleraci vykonávání dotazů
• U prostorových DB je indexace důležitá pro spoustu dotazů – bez indexu by se např. dotaz na nejbližšího souseda daného bodu musel řešit hrubou silou, což je velmi neefektivní • většinou založeny na nějaké aproximaci (diskrétní – mřížka, spojitá – obalovací tvary). • typické akcelerovatelné dotazy patří: ○ nejbližší soused (nearest neighbour) bodu (k-D tree, quad tree, ...), ○ průnik/kolize (obalující tvary, quad tree, …), ○ obsažení, ○ určení vzdáleností apod.
Metody indexace v 1D (nD)
- Rozšíření klasické hashovací tabulky – tato tabulka je dynamická a přidává nové sloty, když je v některém hodně záznamů.
- Díky tomuto lze rozdělit prostorový interval <a></a>
Metody indexace - stromy - k-D strom
staví strom nad k-dimenzionálním prostorem, kde každý uzel je bod v tomto prostoru. Každý vnitřní uzel je bod definující hyperplochu (2D – přímka, 3D – rovina, …) v jednom rozměru prostoru (ty se s hloubkou v stromu pravidelně střídají, např. ve 2D – x, y, x, y, …).
dělí prostor hyperplochami (přímka, plocha) rovnoběžnými s osami, kde tyto hyperplochy obsahují alespoň 1 bod
levé uzly leží nalevo, pravé napravo
statická data
Vyhledávání: OK
vkládání: OK ale vede k degradaci
Mazání: problém - musí dojít k znovusložení stromu
Metody indexace - stromy - adaptivní k-D strom
Na každé straně hyperplochy stejně bodů, body jsou uloženy až v listech, eliminace problému vkládání
vystavění vváženého stromu
Vyhledávání: OK
vkládání: OK
Mazání: OK (stačí odebrat dělící plochu)
Metody indexace - stromy - BSP tree (binary space partitioning)
Podobný jako adaptivní k-D tree ale hyperplochy nemusí procházet body a mohou být libovolně natočené (nemusí být rovnoběžné s osami)
dělí se tak dlouho dokud počet bodů v podprostoru neklesne pod určitou hodnotu (nemusí být 1)
Nepřináší nějaké zlepšení, spíše vyšší nároky na paměť
Metody indexace - stromy - Quad-tree
Jako k-D strom, ale v každé úrovni dělí na 2n podstromů. Např. 3D prostor pokaždé rozdělí na 8 krychlí (ne nutně stejně velkých), každou z nich na dalších 8 podkrychlí atd. Dělí do určitého počtu elementů na podstrom. Existují dvě varianty: point (dělí pomocí bodů) a region (dělí rovnoměrně).
Algoritmus vhodný pro body a regiony
Point quad-tree - dělí v bodech
Region quad-tree - dělí v prostoru na prakticky shodné části
Metody indexace - lineární hashování
Realizuje se pomocí křivek vyplňující prostor (Z-křivka, N křivka, Hilbertova křivka)
Metody indexace - adaptivní hashování - Grid file
Hashování mapuje klíč na malé číslo, podle kterého se vyhledává záznam.
- dělí prostor n-rozměrnou mřížkou
- adresář řadí každou buňku mřízky k datové jednotce (bucket)
výhoda: adresář i mřížka jsou na disku (jen 2 přístupy, 69% využítí paměti)
Nevýhody: vyšší paměťové nároky, při vkládání a mazání bodů nutné přidat či odebrat hyperplochu, u čehož může dojí k zániku či nutnosti přidání hyperplochy
Metody indexace - adaptivní hashování - EXCELL
Jako Grid File, ale dat. jednotky mají stejnou velikost, plus jsou zde přetokové stránky. · dělí na jednotky stejné velikosti · dělení je plošné ○ velký adresář ○ později hierarchie ○ přetokové stránky
Metody indexace - adaptivní hashování - two-level grid file
Dvě úrovně mřížky, první odkazuje na druhou, což je další gid file
změny jsou častěji lokální, ale přetečení není úspěšně vyřešeno (mazání je často lokální)
Metody indexace - adaptivní hashování - twin grid file
Dva nezávislé Grid Files, pokud data v primárním přetečou, ukládají se do druhého (předchází se dělení mřížky)
- rovnoměrné rozložení dat, možnost částečné paralelizace
90% využítí prostoru
Metody indexace - hybridní hashování - BANG (Balanced and Nested Grid File)
Jako grid file, datové buňky se překrývají - podprostory (komibance stromové a hashovací metody)
datová jednotka je v buňce, která je uložena ve vyváženém stromě
Indexovaní vícerozměrných objektů
Indexace bodů je sice převážná část indexování, ale nestačí pro aplikační nasazení. Pro vícerozměrná data se používají stromové struktury a hashování (PLOP, Multi-Layer Grid File, R-File) - tyto struktury se dále také dají indexovat (P-tree)
Transformace (mapování)
Mapuje objekty popsané k body v nD prostoru na body v k*nD prostoru (např. obdélník ve 2D je bod ve 4D). Některé dotazy nejsou realizovatelné, mapování složité, někdy nemožné, problém zpětné transformace výsledku.
Překrývání (vymezování) - R-tree
Buňky se překrývají a datové jednotky (buckets) většinou také, vzniká více možných cest prohledání, ale neví se kolik (problém při paralelizaci).
- jistá skupina se obalí MBB (Minimum bounding box), pokud počet objektů přesáhne mez, rekurzivně se dělí dále
- MBB se mohou překrývat a objekty mohou zasahovat do více buňěk
- algoritmus má stejně vlastnosti jako stromové algoritmy, navíc přibývá problém s více cestami a selektivitou
Ořezávání (duplikace objektů) - R+tree
Buňky se nesmějí překrývat, jediné řešení je pak rozsekat objekty na části podle hranic dotýkajících se bounding boxů. Zpětné shlukování je problém. Při rozšiřování prostoru datových jednotek může dojít k deadlocku, když už se nedá dělit.
objekt se rozděluje pokud zasahuje do více buněk, pokud by hranice nebyly u sebe, musíme vložit další buňku, nebo se buňka rozšíří (potencionální deadlock při nutnosti rozšíření více buněk
R+ tree
- Zástupce metody ořezávání.
- Je podobný R-Tree, ale namísto překrytí dělí objekty na části Pokud objekt zasahuje do více buňek, které nesousedí, je třeba vložit buňku pro střední část nebo rozšířit jednu z buněk (může nastat problém).