Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
Datové struktury pro sketching dynamických množin
Thesis title in Czech: Datové struktury pro sketching dynamických množin
Thesis title in English: Data Structures for Sketching Dynamic Sets
Key words: lineární sketching|rekonstrukce množin|Bloomův filtr|proudové algoritmy|souhrny dat
English key words: linear sketching|set reconstruction|Bloom filter|streaming algorithms|data summaries
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: 21.09.2023
Date of assignment: 26.09.2023
Confirmed by Study dept. on: 09.10.2023
Guidelines
Řešitel si nastuduje nejlepší známé paměťově efektivní datové struktury pro rekonstrukci množin a multimnožin daných dlouhou posloupností přidávání a mazání prvků. Cílem je experimentálně prozkoumat vlastnosti nové datové struktury pro rekonstrukci množin z článku [1] a porovnat ji se starší datovou strukturou zvanou "Invertible Bloom Lookup Table" (IBLT) [2]. Jednou z aplikací, kterou řešitel může prozkoumat, je výpočet symetrických diferencí dvou podobných množin genomických dat [3].
References
[1] Bæk Tejs Houen, Jakob, Rasmus Pagh, and Stefan Walzer. "Simple Set Sketching." In Symposium on Simplicity in Algorithms (SOSA), pp. 228-241. Society for Industrial and Applied Mathematics, 2023.
[2] Goodrich, Michael T., and Michael Mitzenmacher. "Invertible bloom lookup tables." In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 792-799. IEEE, 2011.
[3] Shibuya, Yoshihiro, Djamal Belazzougui, and Gregory Kucherov. "Efficient reconciliation of genomic datasets of high similarity." bioRxiv (2022): 2022-06.
[4] Fleischhacker, Nils, Kasper Green Larsen, Maciej Obremski, and Mark Simkin. "Invertible bloom lookup tables with less memory and randomness." Cryptology ePrint Archive (2023).
[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