Climate and environmental data are characterized by constant changes and although some of them they have been building for decades, these changes are not always smooth and gradual. In fact, the most important changes – called “regime shifts” – are often quite sudden and large. The automatic detection of such changes in large spatio-temporal datasets is critical to monitoring and understanding the behavior of the global climate system. We are investigating multiple facets of the change detection problem: different types of changes (i.e., gradual vs. abrupt, subtle vs. large, etc.) in time series data; characterization of changes through the identification and analysis of change intervals; and changes in spatial structure of the data. The algorithms developed as part of this project are employed in a variety of application settings.