Mining inter-transaction association rules is one of the most interesting issues in data mining research. However, in a data stream environment the previous approaches are unable to find the result of the new-incoming data and the original database without re-computing the whole database. In this paper, we propose an incremental mining algorithm, called DSM-CITI (Data Stream Mining for Closed Inter-Transaction Itemsets), for discovering the set of all frequent inter-transaction itemsets from data streams. In the framework of DSM-CITI, a new in-memory summary data structure, ITP-tree, is developed to maintain frequent inter-transaction itemsets. Moreover, algorithm DSM-CITI is able to construct ITP-tree incrementally and uses the property to avoid unnecessary updates. Experimental studies show that the proposed algorithm is efficient and scalable for mining frequent inter-transaction itemsets over stream sliding windows.
H. Lu, J. Han and L. Feng, Stock movement prediction and N-dimensional inter-transaction association rules, Proceedings of ACM-SIGMOD Workshop on Research Issues on Data Mining and Knowledge, Seattle, USA, June 1998 (ACM, New York, 1998) 12:1-12:7.
2.
H. Lu, L. Feng and J. Han, Beyond intratransaction association analysis: mining multidimensional inter-transaction association rules, ACM Transactions on Information Systems18(4) ( 2000) 423-454.
3.
L. Feng, J.X. Yu, H. Lu et al., A template model for multidimensional inter-transactional association rules, VLDB Journal11(2) (2002) 153-175.
4.
A.K.H. Tung, H. Lu, J. Han et al., Efficient mining of intertransaction association rules, IEEE transactions on Knowledge and Data Engineering15(1) (2003) 43-56.
5.
S. Luhr, G. West and S. Venkatesh, An Extended Frequent Pattern Tree for Intertransaction Association Rule Mining: Technical Report (Curtin University of Technology, Perth, 2005).
6.
A.J.T. Lee and C.S. Wang, An efficient algorithm for mining frequent inter-transaction patterns, Information Sciences28(8) (2007) 3453-3476.
7.
Q. Li, L. Feng and A. Wong, From intra-transaction to generalized inter-transaction: landscaping multidimensional contexts in association rule mining, Information Sciences172(3-4) (2005) 361-395.
8.
J. Chen, L. Ou, J. Yin et al., Efficient mining of cross-transaction web usage patterns in large database, Proceedings of the 7th International Conference on Data Warehousing and Knowledge Discovery, Copenhagen, Denmark, August (2005) 519-528.
9.
H. Chhinkaniwala and P. Santhi Thilagam, InterTARM: FP-tree based framework for mining inter-transaction association rules from stock market data, Proceedings of the 2008 International Conference on Computer Science and Information Technology (ICCSIT 08), Singapore, Singapore , August 2008 (IEEE Computer Society, Los Alamitos, 2008) 513-517.
10.
S.C. Chiu, M.K. Shan, J.L. Huang et al., Mining polyphonic repeating patterns from music data using bit-string based approaches, Proceedings of International Conference on Multimedia and Expo (ICME'09), New York, USA, June 2009 (IEEE Computer Society, Los Alamitos, 2009) 1170-1173.
11.
K.Y. Huang, C.H. Chang and K.Z. Lin, ClosedPROWL: efficient mining of closed frequent continuities by projected window list technology, Proceedings of 5th SIAM International Conference on Data Mining, Houston, USA, November 2005 (ACM, New York, 2005) 501-504.
12.
K.Y. Huang , C.H. Chang and K.Z. Lin , Efficient discovery of frequent continuities by projected window list technology, Journal of Information Science and Engineering24(4) (2008) 1041-1064.
13.
A.J.-T. Lee , C.-S. Wang, W.-Y. Wang, Y.-A. Chen and H.-W. Wu , An efficient algorithm for mining closed inter-transaction itemsets, Data and Knowledge Engineering66(1) (2008) 68-91.
14.
J. Dong and M. Han, IFCIA: An efficient algorithm for mining intertransaction frequent closed itemsets, Proceedings of Fourth International Conference on Fuzzy Systems and Knowledge Discovery2007 ( IEEE Computer Society, Los Alamitos, 2007) 678-682.
15.
B. Babcock, S. Babu, M. Datar et al., Models and issues in data stream systems, Proceedings of the 2002 ACM Symposium on Principles of Database Systems2002 (ACM, New York, 2002) 1-16.
16.
J.H. Chang and W.S. Lee , estWin: Online data stream mining of recent frequent itemsets by sliding window method, Journal of Information Science31(2) (2005) 420-432.
17.
K. Gouda and M. Zaki, Efficiently mining maximal frequent itemsets, Proceedings of the IEEE International Conference on Data Mining, San Jose, USA, November 2001 (IEEE Computer Society, Los Alamitos, 2001) 163-170.
18.
H.F. Li , S.Y. Lee and M.K. Shan, Online mining maximal frequent structures in continuous landmark melody streams, Pattern Recognition Letters26(11) (2005) 1658-1674.
19.
Q. Zou, W. Chu and B. Lu, SmartMiner: A depth first algorithm guided by tail information for mining maximal frequent itemsets, Proceedings of the IEEE International Conference on Data Mining, Maebashi City , Japan, December 2002 (IEEE Computer Society, Los Alamitos, 2002) 570.
20.
H.F. Li and S.Y. Lee , Approximate mining of maximal frequent itemsets in data streams with different window models, Expert Systems with Applications35(3) (2008) 781-789.
21.
J.H. Chang and W.S. Lee , Efficient mining method for retrieving sequential patterns over online data streams, Journal of Information Science31(5) (2005) 420-432.
22.
S. Guha, N. Mishra, R. Motwani et al., Clustering data streams, Proceedings of the Annual Symposium on Foundations of Computer Science, Redondo Beach, November 2000 (IEEE Computer Society, Los Alamitos, 2000) 359-366.
23.
L. O'Callaghan , N. Mishra, A. Meyerson et al., High-performance clustering of streams and large data sets, Proceedings of the 2002 International Conference of Data Engineering, San Francisco, USA, April 2002 (IEEE Computer Society, Los Alamitos, 2002) 685-694.
24.
H. Wang, W. Fan, P.S. Yu et al., Mining concept-drifting data streams using ensemble classifiers , Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, USA, June 2003 (ACM, New York, 2003) 226-235.
25.
W.G. Teng, M.S. Chen and P.S. Yu, A regression-based temporal pattern mining scheme for data streams, Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany, September 2003 (VLDB Endowment, 2003) 99-104.
26.
Y. Chen, G. Dong, J. Han et al., Multi-dimensional regression analysis of time-series data streams . In: Proc. of 2002 International Conference on Very Large Data Bases, Hong Kong, China, August 2002 (VLDB Endowment, 2002) 323-334.
