PhD Defence • Software Engineering • Graph-based Spatial-temporal Cluster Evolution: Representation, Analysis, and Implementation

Please note: This PhD defence will take place in DC 3317.

Ivens Portugal, PhD candidate
David R. Cheriton School of Computer Science

Supervisors: Professors Paulo Alencar, Donald Cowan, Daniel Berry

Spatial-temporal data refers to information about real-world entities that exist in a location, the spatial dimension, and during a period of time, the temporal dimension. These real-world entities, referred to as spatial-temporal objects, such as vehicles or people, may move, group, and continue the movement together, forming clusters. Although there have been significant research efforts to understand cluster, there is a lack of studies that provide methods and software tools to support spatial-temporal cluster evolution, especially those involving spatial-temporal cluster evolution representation and analysis. Understanding this evolution is critical for dealing with spatial-temporal problems related, for example, to service supply and demand, traffic and travel flows, human mobility, and city planning.

This thesis presents an approach to graph-based cluster evolution and its representation, analysis, and implementation. The proposed solution introduces a representation of the structure of a spatial-temporal cluster with the identification of the cluster at several timestamps and linkage, and a representation of the spatial-temporal relationships cluster have during existence with the identification of 14 of such relationships. The proposed solution also introduces a connected representation of cluster evolution using graphs that have nodes as clusters and edges as relationships. The solution provides analysis methods for the structure of spatial-temporal clusters that monitor the changes in location or size over time, and analysis methods for the spatial-temporal cluster relationships the clusters have during existence that calculate the frequency or density of such relationships in specific locations. The solution also provides analysis methods for a graph-based representation of spatial-temporal cluster evolution with integrated results that examine spatial-temporal clusters and their connections, and can provide, for example, aggregated results per location or time of the day, ever-increasing or ever-decreasing regions, growth or decay rates, and measures of similarity between the evolution of two clusters. The approach also provides an implementation of the proposed representation and analysis methods. The approach is evaluated through four case studies using different spatial-temporal datasets to show the results that can be produced, which include, for example, exploratory analyses and specific analyses on ever-increasing and ever-decreasing regions, similarity values, and the movement the clusters represent. Overall, the proposed approach advances research in the spatial-temporal domain by providing novel representation and analysis methods as well as implementation tools that can improve the understanding about how clusters evolve in space and time.