1D přístupové metody

Lineární hashování

Prostor [A,B) dělí na intervaly (B-A)/2^k, či (B-A)/^2k+1, k≥0

• odpovídají stránce, oblasti
• ukazatel t odděluje uz zaplněné intervaly od nezaplněných
• při vložení můze dojít k rozdělení intervalu (jen jednou), i přetečení
• jakmile t dosáhne B, je třeba přerozdělit celý soubor (to sa deje pomerne často)

Adaptivní hashování (modifikace linearniho hashovani)

• jako lineární, ale intervaly jsou nazývány buňkami
• přetokovou oblast řeší adresář
• obsahuje index každé buňky
• jestliže výsek přesáhne kapacitu, dělí se všechny buňky 2
• (na začátku buňka=výsek)
• po dělení více buněk pro výsek
• datové regiony

B-stromy (index-sekvencni struktura)

• hierarchická organizace
• vyvážený (vnořené intervaly)
• uzel ~ stránka ~ interval
• listy - ukazatele na data
• horní/dolní mez na počet následníků
• asi nejadaptabilnější
• pro lineární rozložení je hashování lepší

Štátnicová otázka: Aká je medz pre B-strom – kedy sa považuje za moc prázdny a začne sa zlučovať? (odpoveď: 50%)

Vyhledání/vložení dat

1D data

• Aproximace posloupností celých čísel
• následník/předchůdce
• okolí
• vyspělé algoritmy

2D, 3D, data

• Problém
• chybí uspořádání na více rozměrech
• i když mapování do N, Z, Q existuje
• transformace do 1D
• nesplňuje vlastnosti sousednosti (strácame potrebne vlastnosti)
• pokud je model přípustný, složité transformace dotazů (obtiazne previesť transformáciu spať)

Základní algoritmy pro n-D

• K-D-Tree (Binárny)
• BSP Tree (Binary Space Partitioning - Binárny)
• Quad-Tree (4-arny)
• leží v základu dalších algoritmů
• neřeší problematiku paměti

K-D-Tree

• Prostor je dělen hyper-plochami na nejvyšší úrovni (rovnoběžné s osami)
• Každá plocha musí obsahovat alespoň jeden bod dat
• Vkládání, hledání - OK
• Mazání - problém
• Jen body
• (kamen urazu - listy nesu data)

Modifikace K-D-Tree

Adaptivní K-D-Tree

odstraňuje nevýhodu závislosti na pořadí vkládání (snaží sa tak riešiť problém s mazaním)

data roztroušena po celém stromu

Dělení hyper-plochami probíhá tak, aby na každé straně zbývalo zhruba stejně bodů

I když stále rovnoběžné s osami, hyper-plochy nemusejí obsahovat bod -> data do listů (ve výsledném podprostoru jen jeden bod)

Vhodný pro statická data

Bin-Tree

rekurzivně dělí podprostor na hyperkrychle (shodné velikosti) a. každá obsahuje maximálně jeden bod

BSP-Tree (Binary Space Partitioning)

Jako adaptivní K-D Tree

Dělicí hyper-plochy nejsou (nutně) rovnoběžné s osami

Dělení tak dlouho, dokud počet bodů v podprostoru neklesne pod danou hodnotu

Neadaptivní, vyšší nárok na paměť

Quad-Tree

Shodné s K-D-Tree, ale dělí na 2ⁿ pod-stromů

Pod-stromy nikoliv nutně shodné

Dělení do daného počtu elementů na list (i nula)

Varianta point a region quad-tree

Přístup k bodům - hashování

• Adaptivní hashování
• Grid File
• EXCELL
• Two-Level Grid File
• BANG File
• Twin Grid File
• Lineární hashování
• Hybrid
• Buddy Tree

Adaptivní hashování

Grid File

• Prostor pokryt n-rozměrnou mřížkou
• nikoliv nutně pravidelná
• Výsledné buňky různorodé
• Adresář řadí ka.dou buňku (i více) k datové jednotce (bucket)
• Adresář velký - na disku
• mřížka na disku (jen 2 přístupy na disk)
• Využití prostoru kolem 69%

• Vkládání může způsobit přetečení jednotky (není lokální) (zmena sa neprejaví len v rámci deliacej mriežky, ale zasiahne to aj do ostatných častí a treba to preskladat - môže sa to aj lavínovo síriť)
• rozdělovací hyper-plocha
• možná distribuce skrze strukturu – nárůst adresáře
• Mazání (není lokální)
• odstranění hyper-plochy je třeba prověřit
• odstranění datové jednotky

EXCELL (jako Grid File)

Dělí na jednotky stejné velikosti

Dělení je plošné

• velký adresář
• později hierarchie
• přetokové stránky

Two-Level Grid File

• Mřížka druhé úrovně se používá pro správu adresářů
• kořenový adresář
• pod-adresář (zmeny sa udržujú v podadresári)
• Změny jsou často lokální
• problematika však přesto není zcela uspokojivě řešena

BANG File (Vyvážený Vnorený Grid File)

• Interpolační Grid File je základem
• “řeší“ exponenciální růst adresáře
• buňka = datová jednotka
• Balanced And Nested Grid File
• jako Grid File
• datové jednotky se překrývají (!)
• nemusí mít tvar hyper-krychle
• datové jednotky jsou ve vyváženém stromě

Twin Grid File

• Zdvojená struktura Grid File
• zlepšení využití prostoru
• vztah není hierarchický
• rovnoměrně rozložená data
• využití prostoru až 90% bez „zpomalení“
• jeden ze souborů je „primární“, druhý je „přetokový“
• (žiadny nie je nadriadený/podriadený)

Vícerozměrné lineární hashování

- malé, nebo žádné adresáře (do paměti)

• MOLHPE
• ukazatele pro růst dat
• datové jednotky stejných rozměrů
• nevhodné pro nelineární distribuci
• Quantile hashing
• nerovnoměrně distribuovaná data „zrovnoměrňuje“ - jinak MOLHPE
• Z-hashing
• níže

Buddy Tree

• Adresář je stromová struktura
• minimálně dvě položky (není vyváženo)
• jeden ukazatel na adresář (stránku); lineární
• Strom je rozdělován rekurzivně, dělí se hyper-plochami rovnoběžnými s osami
• Ve vnitřních uzlech se však prostor omezí na MBB (Minimal Bounding Box) vnitřních bodů - selektivita

Přístup k bodům - stromy

• K-D-B-Tree
• hB-Tree
• LSD Tree

K-D-B-Tree (Adaptivny K-D strom + Balancovanie)

• K-D Tree + B-Tree
• Adaptivní K-D Tree
• Balancován (B-Tree)
• Vkládání může způsobit rozdělení
• heuristiky na optimální rozdělení
• propagace stromem (? využití paměti)
• Mazání
• slučování při podtečení

hB-Tree (Holey brick tree)

• Dělení uzlu je více-atributové
• „Fraktální struktura“
• BANG File
• DAG (!) (directed acyclic graph)
• Paralelní verze

LSD Tree (Local split decision)

• Nejen pro prostorová data

(vhodný aj pre iné číselné dáta vo vektore)

• Adaptivní K-D Tree
• Výškově vyvážený strom
• Externí adresářová stránka

Prostorové přístupové body

• Hlavní metody

o       Transformace – mapování (transf. viacrozmerne objekty na niečo iné (napr. 2D na 1D))

o       Překrývání – vymezování (ak dovolíme aby sa objekty prekrývali, musíme ich nejak vymedzovat)

o       Ořezávání - duplikace objektů (nedovolím vymedzujúcim podpriestorom aby sa prekrývali - takže ten veľký objekt musím rezať a duplikovať)

Transformace - mapování

• Objekty v n-D prostoru jsou body v k*n-D prostoru
• obdélník ve 2D je bod ve 4D (např.)
• Optimismus ~> vystřízlivění
• některé dotazy jsou nerealizovatelné
• mapování je složité (nemožné)
• interpretace výsledku

Překrývání

• Datové jednotky se svými hranicemi překrývají
• Často algoritmy zůstávají stejné, jen se počet prohledávaných cest zvětšuje
• dovolene iba prekryvanie - nie vnorovanie

Ořezávání

• Není povoleno překrytí
• Dělení objektů
• Rozšiřování prostoru datových jednotek
• Deadlock (môže dôjsť k tomu že sa to už nedá deliť)
• Dělení datových jednotek

Křivky vyplňující prostor

Z-ordering

Algoritmy

• R-Tree a z něj odvozené
• P-Tree a podobné
• Další hierarchické metody
• Rozšířené K-D Tree
• SKD Tree
• GBD Tree
• Hashovací struktury
• PLOP, Multi-Layer Grid File, R-File

R-Tree (dovoľuje prekrývanie)

R⁺-Tree (nedovoľuje prekrývanie, reže objekty)