TAPER: An Efficient Two-Step Approach for All-Pairs Correlation Query in Transaction Databases

Abstract

Given a user-specified minimum correlation threshold and atransaction database with N items, all-strong-pairs correlation query finds all item pairs with correlations above the threshold. However, when the number of items and transactions are large, the computation cost of this query can be very high. In this paper, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute thanPearson's correlation coefficient but also exhibits a special monotone property which allows pruning of many item pairs even without computing their upper bounds. A two-step all-strong-pairs correlation query (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent or improves when the number of items is increased in data sets with common Zipf or linear rank-support distributions. Experimental results from synthetic and real data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster thanbrute-force alternatives.

Furthermore, as demonstrated by our experiments on both realand synthetic data sets, TAPER can achieve high pruning ratio and outperform brute-force approach several orders of magnitude especially for high correlation thresholds. Finally, in terms of scalability, the pruning ratio of TAPER can be kept no change or even slightly increase with the increase of the number of attributes.