12 - Metody indexování bodových a plošných útvarů - typicky obalujících hyperobdélníků - v prostorových DB

Question 1

Index v prostorových db

Answer 1

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.

Question 2

Metody indexace v 1D (nD)

Answer 2

• 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>

Question 3

Metody indexace - stromy - k-D strom

Answer 3

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

Question 4

Metody indexace - stromy - adaptivní k-D strom

Answer 4

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)

Question 5

Metody indexace - stromy - BSP tree (binary space partitioning)

Answer 5

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ěť

Question 6

Metody indexace - stromy - Quad-tree

Answer 6

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

Question 7

Metody indexace - lineární hashování

Answer 7

Realizuje se pomocí křivek vyplňující prostor (Z-křivka, N křivka, Hilbertova křivka)

Question 8

Metody indexace - adaptivní hashování - Grid file

Answer 8

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

Question 9

Metody indexace - adaptivní hashování - EXCELL

Answer 9

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

Question 10

Metody indexace - adaptivní hashování - two-level grid file

Answer 10

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í)

Question 11

Metody indexace - adaptivní hashování - twin grid file

Answer 11

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

Question 12

Metody indexace - hybridní hashování - BANG (Balanced and Nested Grid File)

Answer 12

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ě

Question 13

Indexovaní vícerozměrných objektů

Answer 13

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