Datové struktury pro sketching dynamických množin
| Název práce v češtině: | Datové struktury pro sketching dynamických množin |
|---|---|
| Název v anglickém jazyce: | Data Structures for Sketching Dynamic Sets |
| Klíčová slova: | lineární sketching|rekonstrukce množin|Bloomův filtr|proudové algoritmy|souhrny dat |
| Klíčová slova anglicky: | linear sketching|set reconstruction|Bloom filter|streaming algorithms|data summaries |
| 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í: | 21.09.2023 |
| Datum zadání: | 26.09.2023 |
| Datum potvrzení stud. oddělením: | 09.10.2023 |
| Datum a čas obhajoby: | 05.09.2024 10:00 |
| Datum odevzdání elektronické podoby: | 17.07.2024 |
| Datum odevzdání tištěné podoby: | 17.07.2024 |
| Datum proběhlé obhajoby: | 05.09.2024 |
| Oponenti: | doc. Mgr. Tomáš Petříček, Ph.D. |
| Zásady pro vypracování |
| Ř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]. |
| Seznam odborné literatury |
| [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. |