Speeding up correlation search for binary data

• Propose a search framework for any good correlation measure.
• Propose a new token-ring algorithm for the top-k search.
• Combine two different searches to overcome the disadvantages of each.

Searching correlated pairs in a collection of items is essential for many problems in commercial, medical, and scientific domains. Recently, a lot of progress has been made to speed up the search for pairs that have a high Pearson correlation (ϕϕ-coefficient). However, ϕϕ-coefficient is not the only or the best correlation measure. In this paper, we aim at an alternative task: finding correlated pairs of any “good” correlation measure which satisfies the three widely-accepted correlation properties in Section 2.1. In this paper, we identify a 1-dimensional monotone property of the upper bound of any “good” correlation measure, and different 2-dimensional monotone properties for different types of correlation measures. We can either use the 2-dimensional search algorithm to retrieve correlated pairs above a certain threshold, or our new token-ring algorithm to find top-k correlated pairs to prune many pairs without computing their correlations. The experimental results show that our robust algorithm can efficiently search correlated pairs under different situations and is an order of magnitude faster than the brute-force method.