The rapid growth of monitoring applications has led to unprecedented amounts of generated time series data. Data analysts typically explore such large volumes of time series data looking for valuable insights. One such insight is finding pairs of time series, in which subsequences of values exhibit certain levels of correlation. However, since exploratory queries tend to be initially vague and imprecise, an analyst will typically use the results of one query as a springboard to formulating a new one, in which the correlation specifications are further refined. As such, it is essential to provide analysts with quick initial results to their exploratory queries, which allows for speeding up the refinement process. This goal is challenging when exploring the correlation in a large search space that consists of a big number of long time series. In this work we propose search algorithms that address precisely that challenge. The main idea underlying our work is to design priority-based search algorithms that efficiently navigate the rather large space to quickly find the initial results of an exploratory query. Our experimental results show that our algorithms outperform existing ones and enable high degree of interactivity in exploring large time series data.