This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Xiong, H. Articles by Ma, S. Search for Related Content

Top-k Correlation Computation

Management Science and Information Systems Department, Rutgers Business School, Rutgers University, Newark, New Jersey 07102
Management Science and Information Systems Department, Rutgers Business School, Rutgers University, Newark, New Jersey 07102
IBM T.J. Watson Research Center, Hawthorne, New York 10532
DoubleClick Inc., New York, New York 10011
hxiong{at}rutgers.edu
wjzhou{at}pegasus.rutgers.edu
mbrodie{at}us.ibm.com
shengma2005{at}gmail.com

Recently, there has been considerable interest in efficiently computing strongly correlated pairs in large databases. Most previous studies require the specification of a minimum correlation threshold to perform the computation. However, it may be difficult for users to provide an appropriate threshold in practice because different data sets typically have different characteristics. To this end, in this paper, we propose an alternative task: finding the top-k strongly correlated pairs. Consequently, we identify a two-dimensional monotone property of an upper bound of correlation coefficient and develop an efficient algorithm, called TOP-COP, to exploit this property to effectively prune many pairs even without computing their correlation coefficients. Our experimental results show that TOP-COP can be an order of magnitude faster than alternative approaches for mining the top-k strongly correlated pairs. Finally, we show that the performance of the TOP-COP algorithm is tightly related to the degree of data dispersion. Indeed, the higher the degree of data dispersion, the larger the computational savings achieved by the TOP-COP algorithm.

Key words: correlation coefficient; Pearson's correlation coefficient; statistical computing
History: received December 2006; accepted December 2007.