Title :
Efficient indexing structures for mining frequent patterns
Author :
Bin Lan ; Ooi, Beng Chin ; Tan, Kian-Lee
Author_Institution :
Dept. of Comput. Sci., Nat. Univ. of Singapore, Singapore
Abstract :
In this paper, we propose a variant of the signature file, called bit-sliced bloom-filtered signature file (BBS), as the basis for implementing filter-and-refine strategies for mining frequent patterns. In the filtering step, the candidate patterns are obtained by scanning BBS instead of the database. The resultant candidate set contains a superset of the frequent patterns. In the refinement phase, each algorithm refines the candidate set to prune away the false drops. Based on this indexing structure, we study two filtering (single and dual filter) and two refinement (sequential scan and probe) mechanisms, thus giving rise to four different strategies. We conducted an extensive performance study to study the effectiveness of BBS, and compared the four proposed processing schemes with the traditional a priori algorithm and the recently proposed FP-tree scheme. Our results show that BBS, as a whole, outperforms the a priori strategy. Moreover, one of the schemes that is based on dual filter and probe refinement performs the best in all cases
Keywords :
data mining; database indexing; FP-tree scheme; a priori algorithm; bit-sliced bloom-filtered signature file; candidate set; dual filter; efficient indexing structures; false drop pruning; filter-and-refine strategies; filtering; frequent pattern mining; frequent pattern superset; performance study; probe refinement; Computer science; Costs; Data mining; Drives; Filtering; Filters; Frequency; Indexing; Probes; Transaction databases;
Conference_Titel :
Data Engineering, 2002. Proceedings. 18th International Conference on
Conference_Location :
San Jose, CA
Print_ISBN :
0-7695-1531-2
DOI :
10.1109/ICDE.2002.994758