Streaming Algorithms for Estimating Quantiles with Novel Error Guarantees
| Název práce v češtině: | Proudové algoritmy pro odhad kvantilů s novými garancemi chyby |
|---|---|
| Název v anglickém jazyce: | Streaming Algorithms for Estimating Quantiles with Novel Error Guarantees |
| Klíčová slova: | proudové algoritmy|prostorová složitost|odhad kvantilů|pravděpodobnostní algoritmy |
| Klíčová slova anglicky: | streaming algorithms|space complexity|quantile estimation|randomized algorithms |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | diplomová práce |
| Jazyk práce: | anglič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í: | 13.09.2023 |
| Datum zadání: | 13.09.2023 |
| Datum potvrzení stud. oddělením: | 19.09.2023 |
| Konzultanti: | Bc. Jakub Tětek |
| Zásady pro vypracování |
| Řešitel nastuduje nejlepší známé proudové (streaming) algoritmy pro odhad kvantilů [1, 2, 3] a pokusí se na základě jejich úprav přispět k porozumění garancí chyb, které leží mezi aditivní a multiplikativní chybou. Jedním z možných směrů je prozkoumat algoritmy, které mají garanci chyby co nejblíže silnější multiplikativní chybě, ale používají paměť srovnatelnou se slabší aditivní chybou. |
| Seznam odborné literatury |
| [1] Karnin, Zohar, Kevin Lang, and Edo Liberty. "Optimal quantile approximation in streams." In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 71-78. IEEE, 2016.
[2] Cormode, Graham, Zohar Karnin, Edo Liberty, Justin Thaler, and Pavel Veselý. "Relative error streaming quantiles." In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 96-108. 2021. [3] Cormode, Graham, Abhinav Mishra, Joseph Ross, and Pavel Veselý. "Theory meets practice at the median: A worst case comparison of relative error quantile algorithms." In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2722-2731. 2021. [4] Cormode, Graham, and Ke Yi. Small summaries for big data. Cambridge University Press, 2020. |