Open Access Open Access  Restricted Access Subscription or Fee Access

Effective Item Set Mining Using Incremental Update Strategy for IMine Index Structure

C. Sathya, Dr.C. Chandrasekar

Abstract


Mining Item set with support constraints are widely used to discovery hidden knowledge from relational DBMS. To reduce the computational complexity of item set extraction, support constraint is enforced on the extracted item sets. Recent existing work, IMine index (Item set-Mine index), provided a structural data representation of transactional data to efficiently extract item set from a relational databases. However the growing demand for frequent updates in the database, necessitates the index structure to adapt to the modified transaction for extracting the item set effectively.

This paper presented an effective incremental update strategy to handle dynamic transaction of the databases for effective item set extraction. The incremental update strategy extract data item without accessing the original transactional, as the index created is not constrained with any support threshold. The update strategy handles the fast and frequent changing transaction and effective extract the data item compared to the existing Imine index structure. The index performance in terms of incremental updates is experimentally evaluated with data sets characterized by different size and data distribution. The experimental results shows better scalability of incremental update strategy for more frequently database updates in terms of transaction size and pattern length. 


Keywords


Item Set Mining, Index Structure, Incremental Update

Full Text:

PDF

References


G. Grahne and J. Zhu, “Mining Frequent Itemsets from Secondary Memory,” IEEE Int’l Conf. Data Mining (ICDM ’04), pp. 91-98, 2004

J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” ACM SIGMOD, 2000

Y.-L. Cheung, “Mining Frequent Itemsets without Support Threshold: With and without Item Constraints,” IEEE Trans. Knowledge and Data Eng., vol. 16, no. 9, pp. 1052-1069, Sept. 2004.

G. Cong and B. Liu, “Speed-Up Iterative Frequent Itemset Mining with Constraint Changes,” IEEE Int’l Conf. Data Mining (ICDM ’02), pp. 107-114, 2002

C.K.-S. Leung, L.V.S. Lakshmanan, and R.T. Ng, “Exploiting Succinct Constraints Using FP-Trees,” SIGKDD Explorations Newsletter, vol. 4, no. 1, pp. 40-49, 2002

T. Uno, M. Kiyomi, and H. Arimura, “LCM ver. 2: Efficient Mining Algorithms for Frequent/Closed/Maximal Itemsets,” IEEE ICDM Workshop Frequent Itemset Mining Implementations (FIMI), 2004.

J. Pei, J. Han, and L.V.S. Lakshmanan, “Pushing Convertible Constraints in Frequent Itemset Mining,” Data Mining and Knowledge Discovery, vol. 8, no. 3, pp. 227-252, 2004.

M. Botta, J.-F. Boulicaut, C. Masson, and R. Meo, “A Comparison between Query Languages for the Extraction of Association Rules,” Fourth Int’l Conf. Data Warehousing and Knowledge Discovery (DaWak), 2002.

E. Baralis, T. Cerquitelli, and S. Chiusano, “Index Support for Frequent Itemset Mining in a Relational DBMS,” 21st Int’l Conf. Data Eng. (ICDE), 2005.

G. Liu, H. Lu, W. Lou, and J.X. Yu, “On Computing, Storing and Querying Frequent Patterns,” Ninth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (SIGKDD), 2003

C. Faloutsos, K.-I. Lin, FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, pages 163–174, San Jose, CA, 1995.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.