Computer Science Research Seminar

11:30 am - 12:30 pm, Wednesday, March 24, 2010

Prof. Jinlin Chen

Queens College/Graduate Center, The City University of New York

Title: BISC: A Bitmap Itemset Support Counting Approach for Efficient Frequent Itemset Mining


Abstract:

The performance of a depth-first frequent itemset (FI) miming algorithm is closely related to the total number of recursions. In previous approaches this is mainly decided by the total number of FIs, which results in poor performance when a large number of FIs are involved. To solve this problem, a three-strategy adaptive algorithm, bitmap itemset support counting (BISC), is presented. The core strategy, BISC1, is used in the innermost steps of the recursion. For a database D with only s frequent items, a depth-first approach need up to s levels of recursions to detect all the FIs (up to 2s). BISC1 completely replaces these recursions with a special summation that directly calculates the supports of all the possible 2^s candidate itemsets. With BISC1 the run-time is entirely independent of the database after one database scan, and the per-candidate cost is only s. To offset the exponential growth of cost (both time and space) with BISC1 as s increases, a second strategy, BISC2, is introduced to effectively double the acceptable range of s. BISC2 divides an itemset into prefix and suffix and improves the performance by pruning all the itemsets with infrequent prefixes. If the total number of frequent items in D is high, the classic database projection strategy is used. In this case for the first s items a single run of BISC (1 or 2) is applied. For each of the remaining items, a projected database is created and the mining process proceeds recursively. To achieve optimal performance, BISC adaptively decides which strategy to use based on the dataset and minimum support. Experiments show that BISC outperforms previous approaches in all the datasets tested. Even though this does not guarantee that BISC will always perform the best, the result is impressive given the fact that most existing algorithms are only efficient in some types of datasets. The memory usage of BISC is also comparable to those of other algorithms.

Biography:

Dr. Jinlin Chen is an associate professor at Computer Science Dept, Queens College/Graduate Center, the City Univ. of New York. Prior to joining CUNY, he was a visiting professor at Univ. of Pittsburg, a researcher at Microsoft Research Asia, and a visiting scholar at Technical University of Munich, Germany. His research interests include Web information modeling and processing, information retrieval/extraction, and data mining. He is a member of the IEEE and ACM. He received his PhD (Electrical Engineering) in 1999, Bachelor degrees ( Electrical Engineering and Economics) in 1994, all from Tsinghua University, China.

For more information about this colloquium, please contact Habib M. Ammari at cschma@hofstra.edu