TAPER: A two-step approach for all-strong-pairs correlation query in large databases

Hui Xiong, Shashi Shekhar, Pang Ning Tan, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


Given a user-specified minimum correlation threshold θ and a market-basket database with N items and T transactions, an 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. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A Two-step All-strong-Pairs corElation 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 of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson's correlation coefficient.

Original languageEnglish (US)
Pages (from-to)493-508
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
StatePublished - Apr 2006

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Association analysis
  • Data mining
  • Pearson's correlation coefficient
  • Statistical computing


Dive into the research topics of 'TAPER: A two-step approach for all-strong-pairs correlation query in large databases'. Together they form a unique fingerprint.

Cite this