Parallel Algorithms for Clustering High-Dimensional Data

Abstract

Shlukování je v Informatice široce studovaný problém s mnoha aplikacemi v růz- ných oblastech. Kvůli značné velikosti instancí vyžaduje shlukování efektivní paralelní algoritmy. V této práci se zaměřujeme na skupinu masivně paralelních algorithmů pro shlukávání postavených na konzistentním geometrickém hešování, kterou vyvinuli Czu- maj a další. Představujeme nové algoritmus pro rychlé konzistení hešování. Dále tyto algoritmy implementujeme a porovnáváme je se současnými protějšky. Pro problém Fa- cility Location naše algoritmy dosahují značného zrychlení nad předchozími algoritmy s drobnou penalizací v ceně řešení. Dále naše algoritmy srovnáváme s algoritmy pro k- medián a k-means z Pythoní knihovny scikit-learn. V případě k-mediánu naše algoritmy je překnovávají a jsou narozdíl od Pythoních schopné počítat velké vstupy. Široce po- užívány a značně zoptimalizovaný algoritmus k-means++, se kterým se srovnáváme, se ukázal jako rychlejší a vydal lepší výsledky.

Clustering is a widely studied problem in computer science with many applications across fields. Due to the large size of clustering instances, this problem calls for effi- cient parallel algorithms. In this thesis, we focus on a set of massively parallel clustering algorithms based on consistent geometric hashing designed by Czumaj et al. We intro- duce a new algorithm for fast consistent geometric hashing. Next, we implement these algorithms and compare them to current state-of-the-art algorithms. For Facility Loca- tion, our algorithms greatly outperform the speed of previous algorithms while producing solutions with small or no cost increase. For k-median and k-means, we compare our al- gorithms to Python's scikit-learn ones. For k-median, we provide solutions outclassing current ones and being able to compute larger inputs, unlike baselines. For k-means, scikit's widely used and highly optimised k-means++ proved better than our algorithms.