Department of Computer Science at UH

University of Houston

Department of Computer Science

In Partial Fulfillment of the Requirements for the Degree of
Doctor of Philosophy

Chun-Sheng Chen

Will defend his dissertation

Towards Better and Faster Spatial Clustering Algorithms


Finding interesting patterns in spatial data sets is essential for many applications. Spatial data sets have unique characteristics, for instance autocorrelation, the continuous nature of space, complex spatial data types, the importance of maps as summaries, and the necessity to deal with a large number of potential patterns. However, traditional data mining techniques do not take the unique characteristics of spatial data into consideration; consequently, they do not perform well for applications of this kind.

In this study, we approach spatial clustering from two different directions. The first part of the dissertation centers on utilizing supervised density estimation techniques for spatial clustering. Two novel density-based clustering algorithms DCONTOUR, and DENTRAC for clustering spatial point and trajectory data are introduced and analyzed. Moreover, since DCONTOUR uses polygons as models for spatial clusters, polygon-based spatial post-analysis techniques are proposed which characterize and mine spatial clusters. The second part of the research addresses the need to have an efficient clustering algorithm for large spatial data sets. A representative-based spatial clustering algorithm named CLEVER is parallelized in this study. Different parallel computing paradigms including OpenMP and GPU computing (Nvidia CUDA) are investigated for this purpose. Parallel implementations of CLEVER achieved up to 100 time speed up compared to its sequential counterpart for benchmark data sets ranging between 3,000 and 2,000,000 objects.

Date: Tuesday, July 26, 2011
Time: 10:30 AM
Place: 550-PGH
Faculty, students, and the general public are invited.
Advisor: Prof Christoph F. Eick