Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
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:
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
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.
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html