Algoritmy pro rozsáhlá data doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Základní informace

• Vše potřebné bude komunikováno na přednášce či hromadným emailem.

Poznámky a materiály k přednáškám

1. Úvod, hashování - viz text po str. 19.
2. Hashování - text po str. 24 a text Martina Mareše
3. Lineární sondování a Robin Hood hashing. Konzistentní hashování -- hashring a chord - text od str. 27 plus animace ve slajdech a předchozí text M. Mareše.
4. Bloomovy filtry - text od str. 40
5. Heavy Hitters a Count-Min Sketch - text od str. 65 a text ze Stanfordu
6. Kardinalita a (Hyper)LogLog - text od str. 84 a článek
7. Model externí paměti - text od str. 123
8. B-stromy a jejich varianty - text od str. 138 - a texty D. Mount, lecture notes a D. Comer, Ubiquitous B-Tree, případně J. Wyss-Gallifent. A ještě něco k B*-stromům.
9. B^ε-stromy a LSM-stromy - text od str. 151 a články An Introduction to B^ε-trees and Write-Optimization a LSM-based Storage Techniques: A Survey
10. Řazení v externí paměti - text od str. 163 a kapitola 1.2 a Good pivots na str. 36.
11. Streamovaní dat - text str. 101-113, doplňující text zde.

Domácí úkol 1

• Vše porovnáváno na stejném datasetu.
• Opravy neposílejte, bude použita pouze první verze.

Domácí úkol 2

Domácí úkol 3 - zápočtový

Domácí úkol 4 - zápočtový

Domácí úkol 5

Domácí úkol 6