Top-k φ Correlation Computation

Top-k φ Correlation Computation

0.00 Avg rating0 Votes
Article ID: iaor200952635
Country: United States
Volume: 20
Issue: 4
Start Page Number: 539
End Page Number: 552
Publication Date: Sep 2008
Journal: INFORMS Journal On Computing
Authors: , , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.