Last update: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)
This course focuses on streaming algorithms that are used to
sequentially process massive datasets using low memory. As a result, they
produce a concise summary of the dataset that approximately preserves
relevant data properties. We will cover basic problems such as counting
distinct elements, estimating quantiles and random sampling, as well as
algorithms for graph or geometric streams. We will also discuss how to prove
lower bounds in this model using communication complexity. Since streaming
algorithms typically employ randomness, we will assume knowledge on the
level of the course
Last update: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)
Obsahem této přednášky budou tzv. proudové (streaming)
algoritmy, které se používají k sekvenčnímu zpracování velkých dat s malou
pamětí. Zaměříme se na základní problémy, např. počítání různých prvků,
odhad kvantilů a náhodné vzorkování (sampling), probereme algoritmy pro
grafové nebo geometrické proudy dat a také si ukážeme, jak lze dokazovat
dolní odhady v tomto výpočetním modelu. Jelikož proudové algoritmy jsou
často pravděpodobnostní, předpokládají se znalosti na úrovni předmětu
NTIN022 Pravděpodobnostní techniky.
Literature
Last update: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)
Graham Cormode, Ke Yi: Small summaries for Big Data, 2020.
Amit Chakrabarti: Lecture Notes on Data Stream Algorithms, 2020.
