Proudové algoritmy pro Lp vzorkování velkých dat
| Název práce v češtině: | Proudové algoritmy pro Lp vzorkování velkých dat |
|---|---|
| Název v anglickém jazyce: | Streaming Algorithms for Lp Sampling from Large Datasets |
| Klíčová slova: | vzorkování|lineární sketching|proudové algoritmy|souhrny dat|algoritmus precision sampling|vzorkování nezávislé na frekvenci |
| Klíčová slova anglicky: | sampling|linear sketching|streaming algorithms|data summaries|precision sampling algorithm|distinct sampling |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | Mgr. Pavel Veselý, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 19.04.2024 |
| Datum zadání: | 19.05.2024 |
| Datum potvrzení stud. oddělením: | 20.05.2024 |
| Datum a čas obhajoby: | 05.09.2024 10:00 |
| Datum odevzdání elektronické podoby: | 18.07.2024 |
| Datum odevzdání tištěné podoby: | 18.07.2024 |
| Datum proběhlé obhajoby: | 05.09.2024 |
| Oponenti: | Mgr. Tung Anh Vu |
| Zásady pro vypracování |
| Řešitel si nastuduje nejlepší známé proudové (streaming) algoritmy pro vzorkování (sampling) velkých dat. Konkrétně se zaměří na vzorkování s pravděpodobností nezávislou na počtu výskytu prvků na vstupu (tzv. "distinct sampling") a na vzorkování s pravděpodobností úměrnou druhé mocnině frekvence prvku a to pomocí algoritmu "Precision Sampling" nebo alternativních přístupů. Cílem je experimentálně vyhodnotit efektivitu těchto algoritmů a to na náhodně generovaných i reálných datech (např. genomických), případně navrhnout praktická vylepšení nebo porovnat různé přístupy. |
| Seznam odborné literatury |
| [1] Cormode, Graham, and Donatella Firmani. "A unifying framework for ℓ_0-sampling algorithms." Distributed and Parallel Databases 32 (2014): 315-335.
[2] Andoni, Alexandr, Robert Krauthgamer, and Krzysztof Onak. "Streaming algorithms via precision sampling." 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE, 2011. [3] Cormode, Graham, and Hossein Jowhari. "L_p samplers and their applications: A survey." ACM Computing Surveys (CSUR) 52.1 (2019): 1-31. [4] Jayaram, Rajesh, David P. Woodruff, and Samson Zhou. "Truly perfect samplers for data streams and sliding windows." Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 2022. [5] Cormode, Graham, and Ke Yi. Small summaries for big data. Cambridge University Press, 2020. |