Proudové algoritmy pro Lp vzorkování velkých dat
| Thesis title in Czech: | Proudové algoritmy pro Lp vzorkování velkých dat |
|---|---|
| Thesis title in English: | Streaming Algorithms for Lp Sampling from Large Datasets |
| Key words: | vzorkování|lineární sketching|proudové algoritmy|souhrny dat|algoritmus precision sampling|vzorkování nezávislé na frekvenci |
| English key words: | sampling|linear sketching|streaming algorithms|data summaries|precision sampling algorithm|distinct sampling |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | Mgr. Pavel Veselý, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 19.04.2024 |
| Date of assignment: | 19.05.2024 |
| Confirmed by Study dept. on: | 20.05.2024 |
| Date and time of defence: | 05.09.2024 10:00 |
| Date of electronic submission: | 18.07.2024 |
| Date of submission of printed version: | 18.07.2024 |
| Date of proceeded defence: | 05.09.2024 |
| Opponents: | Mgr. Tung Anh Vu |
| Guidelines |
| Ř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. |
| References |
| [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. |