Time series collections are abundant in many disciplines of science, especially those dealing with Earth observation data like vegetation levels, precipitation or surface temperature measurements. Correlation analysis for all pairs of time series is often the first step of exploratory data analysis since it can reveal causal relationships hidden in the data. When exploring large collections of time series, pairwise correlation computations are a significant challenge due to the inherent quadratic complexity of the problem. In many real-world time series collections the time series naturally group into clusters with highly similar behavior. We exploit this natural structure to rapidly approximate the full pairwise correlation matrix for a time series collection without computing all pairwise correlations. The main idea of our estimation algorithm COREQ (CORrelation EQuivalence) is to compute equivalence classes of highly correlated time series and pool redundant correlation estimates into a single class estimate.