The ability to address important questions about the degree of climate change and its potential impacts requires a deeper understanding of the complex dependence structures inherent in climate, such as nonlinear associations or long-range spatial dependencies (teleconnections). Examples include (1) understanding the relationship of fire size and frequency to precipitation, land cover, ocean temperature, etc., and (2) understanding the impact of sea surface temperature on hurricane frequency and intensity. Currently, relationships are typically discovered by the targeted investigations of highly trained scientists of the phenomena of interest, as in the recent discovery that different patterns of warming in the Pacific Ocean have different effects on the frequency and tracks of North Atlantic cyclone. Although such manual approaches may produce quite noteworthy results, they may miss important relationships, and thus, we are developing new data-driven approaches for finding these spatio-temporal and potentially nonlinear relationships. The ability to find and incorporate complex dependence structures has the potential to offer significant advances in climate sciences.