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, ak. r. 2024/2025

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. (Pozor, zde používáme verzi B-stromů s rotací, jak definováno v původním článku od Bayer, R., McCreight, E.M. Organization and maintenance of large ordered indexes. Acta Informatica 1, 173–189 (1972). Varianta z ALGO2 se liší, neboť je postavena na článku Guibas, L.J., Sedgewick, R. A dichromatic framework for balanced trees, FOCS 1978, viz uvedený Comerův článek)
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.