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

1
Q

Index v prostorových db

A

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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Metody indexace v 1D (nD)

A
  • 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>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Metody indexace - stromy - k-D strom

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Metody indexace - stromy - adaptivní k-D strom

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Metody indexace - stromy - Quad-tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Metody indexace - lineární hashování

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Metody indexace - adaptivní hashování - EXCELL

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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ě

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Indexovaní vícerozměrných objektů

A

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).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly