Fast Parallel Algorithms and Library for Spatial Clustering and Computational Geometry

This thesis presents novel parallel shared-memory multi-core algorithms, implementations, and frameworks for efficiently solving large-scale spatial clustering and computational geometry problems. The primary focus is on designing theoretically-efficient and practical algorithms that can handle the increasing demand for faster processing speeds in spatial data sets. In the first part of the thesis, we introduce new parallel algorithms and framework for spatial clustering. We design new parallel algorithms for exact and approximate DBSCAN, which match the work complexity of the best sequential algorithms while maintaining low depth. Extensive experiments demonstrate that our algorithms achieve massive speedup over existing algorithms and can efficiently process large-scale data sets. We also present new parallel algorithms for hierarchical DBSCAN (HDBSCAN) and Euclidean minimum spanning tree (EMST), including several theoretical results and practical optimizations. Furthermore, we propose a method to generate a dendrogram from the minimum spanning tree (MST) of the HDBSCAN or EMST problem. The EMST also solves single-linkage clustering. Lastly, we also design a framework for implementing parallel grid-based clustering algorithms. The second part of the thesis introduces our contributions to parallel algorithms and a library for computational geometry. We contribute to three problems in computational geometry: a new parallel reservation-based algorithm that can express both randomized incremental convex hull and quickhull algorithms; a sampling-based algorithm to reduce work for the smallest enclosing ball problem; and a parallel batch-dynamic data structure for dynamic closest pair problem. We also introduce ParGeo, a library for parallel computational geometry that provides various parallel geometric algorithms, data structures, and graph generators. Our experimental evaluations show significant speedups achieved by our proposed algorithms across different problems. Overall, this thesis demonstrates that parallel shared-memory multi-core algorithms, implementations, and frameworks can efficiently solve large-scale spatial clustering and computational geometry problems both in theory and practice.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Wang, Yiqiu

Advisor dc:contributor.advisor

• Shun, Julian

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/151320

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/151320