Mining Relationships in Spatio-temporal Datasets

The generation of spatio-temporal datasets has seen a phenomenal growth in the past few years with the advances in remote sensing and location sensing devices. Data in many domains like climate, remote sensing, mobile computing, network monitoring, etc. are characterized by spatial and temporal dimensions and have features like spatial and temporal autocorrelation, complex dependence structures such as non linear associations, time lagged associations and long-range spatial dependencies (also known as teleconnections). Traditional methods of data mining usually handle spatial and temporal dimensions separately and thus are not very effective to capture the dynamic relation- ships and patterns in spatio-temporal datasets. In this thesis, we present methods and algorithms to analyze the spatio-temporal datasets and to discover patterns. In particular, the focus of the thesis is on finding a key kind of patterns known as teleconnections. Teleconnections are recurring patterns in climate anomalies connecting two regions that are far apart from each other. They have been a subject of interest to climatologists due to the possibility of the linkages in the changes in weather at one location to the changes at another distant location. Two of the most important teleconnection patterns are the El Nino Southern Oscillation (ENSO) and the North Atlantic Oscillation (NAO). These teleconnections are important to study in climate because they are known to impact precipitation and temperature anomalies at large parts of the globe. Scientists have known of the existence of a number of these relationships and historically they have been discovered by human observation or by using pattern analysis techniques such as the Empirical Orthogonal Function (EOF) over a limited region. However there are several limitations of the existing methods of finding these relationships, and they required considerable research and insight on the part of the domain experts involved. This thesis aims to provide systematic data guided approaches to find such relationships in spatio-temporal data. Discovery of relationships or dependencies among climate variables involved is extremely challenging due to the nature and massive size of the data. In this thesis, we provide a graph based approach to find these patterns in climate datasets. Our approach generates a single snapshot picture of all the teleconnections on the globe and hence it enables us to precisely study the interactions and changes in behavior over time. We are able to identify most of the known connections with a high precision. Further, we show that some of the indices discovered using data guided approaches can capture the impact on temperature anomalies with a much higher correlation as compared to the static indices used by climate scientists. We also extend the algorithm to find time lagged relationships in climate data which are important to study as they add predictive power to these relationships. We further provide an algorithm to test the significance of the teleconnection patterns. Significance testing in a spatio-temporal setting needs to take into account the various characteristics of spatio-temporal datasets like non-i.i.d. data, trends, seasonality, etc. Our approach takes into account all these aspects of the datasets and helps us to remove spurious edges thus potentially enabling us to find new connections. This thesis shows that data guided approaches offer a huge potential for characterizing and discovering unknown relationships and thus advancing climate science.