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 |
| Date and time of defence: | 05.09.2024 10:00 |
| Date of electronic submission: | 17.07.2024 |
| Date of submission of printed version: | 17.07.2024 |
| Date of proceeded defence: | 05.09.2024 |
| Opponents: | Mgr. Tomáš Petříček, Ph.D. |
| 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. |