【Topic】TOP-K Phi Correlation Computation

【Speaker】Hui Xiong

【Time】2007-5-29 10:30-12:00

【Venue】302, Shunde Building

【Language】English

【Organizer】Department of Management Science and Engineering

【Target Audience】

【Background Information】

Abstract:

The problem of association pattern mining is to develop techniques for finding groups of highly-correlated objects from massive data. This problem is important for various application domains, such as homeland security, market basket study, and biomedical data analysis. A large body of association mining work was motivated by the difficulty of efficiently identifying highly correlated objects using traditional statistical correlation measures. This has led to the use of alternative interest measures, such as support and confidence, despite the lack of aprecise relationship between these new interest measures and statistical correlation measures. However, this approach tends to generate too many spurious patterns involving objects which are poorly correlated. In this talk, we provide a precise relationship between Phi correlationcoefficient and the support measure. We also identify a 2-D monotone property of an upper bound of Phi correlation coefficient and develop an efficient algorithm, called TOP-COP to exploit this property to effectively prune many pairs even without computing their correlationcoefficients. 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.

Brief Biography:

Hui Xiong is currently an Assistant Professor in the Management Science and Information Systems Department atRutgers- the State University of New Jersey, USA. He received the Ph.D. degree in Computer Science from theUniversityofMinnesota,USA, in 2005, the B.E. degree in Automation from theUniversityofScienceand Technology of China, and the M.S.degree in Computer Science from the National University of Singapore. His research interests include data mining, spatial databases, statistical computing, and Geographic Information Systems (GIS) with applications in business, database security, self-managing systems, andbio-medical informatics. He has published over 30 papers in the refereed journals and conference proceedings, such as IEEE Transactions on Knowledge and Data Engineering, VLDB Journal, Data Mining and Knowledge Discovery Journal, ACM SIGKDD, SIAM SDM, IEEE ICDM, ACM CIKM, ACM GIS, and PSB. He is the co-editor of the book entitled "Clustering and Information Retrieval", the author of a monograph entitled "Hypercliquepattern discovery: Algorithms and applications", and the co-Editor-in-Chief of Encyclopedia of Geographical Information Science. He has also served on the organization committees and the program committees of a number of conferences, such as ACM SIGKDD, SIAM SDM,IEEE ICDM, IEEE ICTAI, ACM CIKM, and IEEE ICDE. Dr. Xiong is a member of the IEEE Computer Society, the ACM, and the Sigma Xi.