Parallel Algorithms for Clustering High-Dimensional Data

• Název práce v češtině: Paralelní algoritmy pro shlukování dat ve vysoké dimenzi
• Název v anglickém jazyce: Parallel Algorithms for Clustering High-Dimensional Data
• Klíčová slova: shlukování|masivně paralelní výpočty|paralelní algoritmy|k-medián|k-means
• Klíčová slova anglicky: clustering|massively parallel computation|parallel algorithms|k-median|k-means
• Akademický rok vypsání: 2024/2025
• Typ práce: bakalářská 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í: 11.09.2024
• Datum zadání: 11.09.2024
• Datum potvrzení stud. oddělením: 11.09.2024
• Datum odevzdání elektronické podoby: 07.05.2025

Zásady pro vypracování

Řešitel si nastuduje nové masivně paralelní algoritmy pro nehierarchickou shlukovou analýzu dat [1], konkrétně pro řešení problémů jako je Facility Location, k-medián nebo k-means. Tyto algoritmy implementuje v C++ a experimentálně vyhodnotí z hlediska kvality řešení a doby běhu v porovnání s neparalelní verzí algoritmu [2] a s dalšími paralelními algoritmy, které používají jiné techniky, např. [3]. Pro experimenty budou použity jak uměle vygenerované instance, tak reálná data použitá např. v [3]. Cílem je dostat efektivní implementaci algoritmů navržených v teoretickém článku [1], což bude vyžadovat jejich praktické úpravy.

Práce navazuje na řešitelův ročníkový projekt "clustering".

Seznam odborné literatury

[1] Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý: Fully-Scalable MPC Algorithms for Clustering in High Dimension. ICALP 2024: 50:1-50:20

[2] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816–832, 2003

[3] Vincent Cohen-Addad, Vahab S. Mirrokni, Peilin Zhong: Massively Parallel k-Means Clustering for Perturbation Resilient Instances. ICML 2022: 4180-4201

[4] Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson: Parallel and Efficient Hierarchical k-Median Clustering. NeurIPS 2021: 20333-20345

[5] Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii: Massively Parallel Computation: Algorithms and Applications. Found. Trends Optim. 5(4): 340-417 (2023)