Abstract
Mining generalized association rules among items in the presence of taxonomies has been recognized as an important model in data mining. Earlier work on mining generalized association rules ignore the fact that the taxonomies of items cannot be kept static while new transactions are continuously added into the original database. How to effectively update the discovered generalized association rules to reflect the database change with taxonomy evolution and transaction update is a crucial task. In this paper, we examine this problem and propose a novel algorithm, called IDTE, which can incrementally update the discovered generalized association rules when the taxonomy of items is evolved with new transactions insertion to the database. Empirical evaluations show that our algorithm can maintain its performance even in large amounts of incremental transactions and high degree of taxonomy evolution, and is more than an order of magnitude faster than applying the best generalized associations mining algorithms to the whole updated database.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Imielinski, T., Swami, A.: Mining Association Rules between Sets of Items in Large Databases. In: Proc. 1993 ACM-SIGMOD Intl. Conf. Management of Data, pp. 207–216 (1993)
Agrawal, R., Srikant, R.: Fast Algorithms for Mining Association Rules. In: Proc. 20th Intl. Conf. Very Large Data Bases, pp. 487–499 (1994)
Brin, S., Motwani, R., Ullman, J.D., Tsur, S.: Dynamic Itemset Counting and Implication Rules for Market Basket Data. SIGMOD Record 26, 255–264 (1997)
Cheung, D.W., Han, J., Ng, V.T., Wong, C.Y.: Maintenance of Discovered Association Rules in Large Databases: An Incremental Update Technique. In: Proc. 1996 Int. Conf. Data Engineering, pp. 106–114 (1996)
Cheung, D.W., Ng, V.T., Tam, B.W.: Maintenance of Discovered Knowledge: A case in Multi-level Association Rules. In: Proc. 1996 Int. Conf. Knowledge Discovery and Data Mining, pp. 307–310 (1996)
Cheung, D.W., Lee, S.D., Kao, B.: A General Incremental Technique for Maintaining Discovered Association Rules. In: Proc. DASFAA 1997, pp. 185–194 (1997)
Han, J., Fu, Y.: Dynamic Generation and Refinement of Concept Hierarchies for Knowledge Discovery in Databases. In: Proc. AAAI 1994 Workshop on Knowledge Discovery in Databases (KDD 1994), pp. 157–168 (1994)
Han, J., Fu, Y.: Discovery of Multiple-level Association Rules from Large Databases. In: Proc. 21st Intl. Conf. Very Large Data Bases, Zurich, Switzerland, pp. 420–431 (1995)
Hong, T.P., Wang, C.Y., Tao, Y.H.: Incremental Data Mining Based on Two Support Thresholds. In: Proc. 4th Int. Conf. Knowledge-Based Intelligent Engineering Systems and Allied Technologies, pp. 436–439 (2000)
Ng, K.K., Lam, W.: Updating of Association Rules Dynamically. In: Proc. 1999 Int. Symp. Database Applications in Non-Traditional Environments, pp. 84–91 (2000)
Park, J.S., Chen, M.S., Yu, P.S.: An Effective Hash-based Algorithm for Mining Association Rules. In: Proc. 1995 ACM SIGMOD Intl. Conf. on Management of Data, San Jose, CA, USA, pp. 175–186 (1995)
Savasere, A., Omiecinski, E., Navathe, S.: An Efficient Algorithm for Mining Association Rules in Large Databases. In: Proc. 21st Intl. Conf. Very Large Data Bases, pp. 432–444 (1995)
Sarda, N.L., Srinivas, N.V.: An Adaptive Algorithm for Incremental Mining of Association Rules. In: Quirchmayr, G., Bench-Capon, T.J.M., Schweighofer, E. (eds.) DEXA 1998. LNCS, vol. 1460, pp. 240–245. Springer, Heidelberg (1998)
Srikant, R., Agrawal, R.: Mining Generalized Association Rules. In: Proc. 21st Int. Conf. Very Large Data Bases, pp. 407–419 (1995)
Thomas, S., Bodagala, S., Alsabti, K., Ranka, S.: An Efficient Algorithm for the Incremental Updation of Association Rules in Large Databases. In: Proc. 3rd Int. Conf. Knowledge Discovery and Data Mining (1997)
Tseng, M.C., Lin, W.Y.: Maintenance of Generalized Association Rules with Multiple Minimum Supports. Intelligent Data Analysis 8, 417–436 (2004)
Zaki, M.J.: Scalable Algorithms for Association Mining. IEEE Transactions on Knowledge and Data Engineering 12(2), 372–390 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tseng, MC., Lin, WY., Jeng, R. (2005). Maintenance of Generalized Association Rules Under Transaction Update and Taxonomy Evolution. In: Tjoa, A.M., Trujillo, J. (eds) Data Warehousing and Knowledge Discovery. DaWaK 2005. Lecture Notes in Computer Science, vol 3589. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11546849_33
Download citation
DOI: https://doi.org/10.1007/11546849_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28558-8
Online ISBN: 978-3-540-31732-6
eBook Packages: Computer ScienceComputer Science (R0)