Abstract
New transaction insertions and old transaction deletions may lead to previously generated association rules no longer being interesting, and new interesting association rules may also appear.
Existing association rules maintenance algorithms are Apriori-like, which mostly need to scan the entire database several times in order to update the previously computed frequent or large itemsets, and in particular, when some previous small itemsets become large in the updated database.
This paper presents two new algorithms that use the frequent patterns tree (FP-tree) structure to reduce the required number of database scans. One proposed algorithm is the DB-tree algorithm, which stores all the database information in an FP-tree structure and requires no re-scan of the original database for all update cases. The second algorithm is the PotFp-tree (Potential frequent pattern) algorithm, which uses a prediction of future possible frequent itemsets to reduce the number of times the original database needs to be scanned when previous small itemsets become large after database update.
This research was supported by the Natural Science and Engineering Research Council (NSERC) of Canada under an operating grant (OGP-0194134) and a University of Windsor grant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R. and Srikant, R.: Fast Algorithms for Mining Association Rules in Large Databases, In Proceedings of the 20th International Conference on very Large Databases, Santiago, Chile, 1994, pp. 487–499.
Cheung, D. W., Han, J., Ng, V. T., Wong, C. Y.: Maintenance of Discovered Association Rules in Large Database: An I ncremental Updating Technique, In Proceedings of the 12th International Conference on Data Engineering, New Orleans, Louisiana, 1996.
Cheung, D. W., Lee, S. D., Kao, B.: A General Incremental Technique for Maintaining Discovered Association Rules, In Proceedings of the Fifth International Conference on Database Systems for Advanced Applications, Melbourne, Australia, Jan, 1997.
Han, J., Kamber, M.: Data Mining-Concepts and Techniques, Morgan Kaufmann Publisher, 2001.
Han, J., Pei, J., Yin, Y.: Mining Frequent Patterns without Candidate Generation, ACM SIGMOD 2000, Dallas, TX, U. S. A.
Holsheimer, M., Kersten, H., Mannila, M., Toivonen, H.: A Perspective on Databases and Data Mining. First International conference on Knowledge, Discovery and data Mining, Montreal, canada, AAAI Press, 1995, pp. 150–155.
Park, J. S., Chen, M. S., Yu, P. S., An Effective Hashed Based Algorithm for Mining Association Rules, In Proceedings of the ACM SIGMOD Conference on Management of Data, San Jose, California, may, 1995.
Zhou, Z., Ezeife, C. I.: A Low-Scan Incremental Association Rule Maintenance Method Based on the Apriori Property, in the Proceedings of the fourteenth Canadian Conference on Artificial Intelligence, AI 2001, June, 2001, Ottawa.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ezeife, C.I., Su, Y. (2002). Mining Incremental Association Rules with Generalized FP-Tree. In: Cohen, R., Spencer, B. (eds) Advances in Artificial Intelligence. Canadian AI 2002. Lecture Notes in Computer Science(), vol 2338. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47922-8_13
Download citation
DOI: https://doi.org/10.1007/3-540-47922-8_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43724-6
Online ISBN: 978-3-540-47922-2
eBook Packages: Springer Book Archive