Parallel Algorithms for High-Dimensional Clustering
Discipline: Computer Sciences and Information Management
Subcategory: Computer Science & Information Systems
Session: 1
Room: Chinatown
Papa K. Manu - University of Maryland Baltimore County
Co-Author(s): Mohammed Ajabnoor, University of Michigan, MI; Benjamin Landrum, University of Maryland Collegepark, MD; Andrew Brady, University of Richmond, VA;
Clustering is the partitioning of a dataset into related subsets. It can be used in many areas such as bioinformatics, machine learning, and data science. A widely used clustering method is k-means which is a centroid-based clustering algorithm. There are two main categories of k-means algorithms: exact and approximate. Exact k-means is the gold standard that uses exact distance computations. However, it can be computationally expensive. On the other hand, approximate k-means reduces computational complexity but does not utilize exact distance computations. One of the classic exact k-means clustering algorithms is called Lloyd’s k-means algorithm [1]. Many works have created exact k-means algorithms that speed up Lloyd’s algorithm by cutting down on unnecessary calculations. One such example is the Yinyang k-means algorithm [2]. Unfortunately, even accelerated exact k-means algorithms are still too slow to handle massive queries of industrial interest such as clustering 1 billion points with 128 dimensions into 100,000 centers. This summer, we implemented parallelized versions of different k-means algorithms using ParlayLib, a scalable parallel coding library in C++ [3]. We have also parallelized various initialization methods for k-means as well as worked on developing and parallelizing different approximate k-means methods. We plan to continue developing these parallelized approximate k-means methods as well as benchmark our algorithms against existing state-of-the-art implementations to showcase the scalability and accuracy of our ideas.References: [1] S. Lloyd. “Least squares quantization in PCM”. In: IEEE Transactions on Information Theory 28.2 (Mar. 1982), pp. 129-137. issn: 1557-9654. doi: 10.1109/TIT. 1982.1056489.[2] Yufei Ding et al. “Yinyang K-Means: A Drop-in Replacement of the Classic K-Means with Consis- tent Speedup”. In: Proceedings of the 32nd International Conference on International Conference on Machine Learning – Volume 37. ICML’15. Lille, France: JMLR.org, 2015, pp.579-587.[3] Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib – A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 507-509.
Funder Acknowledgement(s): UMD, NSF
Faculty Advisor: Laxman Dhulipala, laxman@umd.edu
Role: I aided in accelerating different k-means algorithms (both exact and approximate). I also aided in data visualization used to create the graphs in the presentation.