Maintenance of fast updated frequent pattern trees for record deletion. (English) Zbl 1453.62111
Summary: The Frequent-Pattern-tree (FP tree) is an efficient data structure for association-rule mining without generation of candidate itemsets. It was used to represent a database into a tree structure which stored only frequent items. It, however, needed to process all transactions in a batch way. In the past, Hong et al. thus proposed an efficient incremental mining algorithm for handling newly inserted transactions. In addition to record insertion, record deletion from databases is also commonly seen in real-applications. In this paper, we thus attempt to modify the FP-tree construction algorithm for efficiently handling deletion of records. A fast updated FP-tree (FUFP-tree) structure is used, which makes the tree update process become easier. An FUFP-tree maintenance algorithm for the deletion of records is also proposed for reducing the execution time in reconstructing the tree when records are deleted. Experimental results also show that the proposed FUFP-tree maintenance algorithm for deletion of records runs faster than the batch FP-tree construction algorithm for handling deleted records and generates nearly the same tree structure as the FP-tree algorithm. The proposed approach can thus achieve a good trade-off between execution time and tree complexity.
MSC:
| 62-08 | Computational methods for problems pertaining to statistics |
References:
| [1] | Agrawal, R., Imielinksi, T., Swami, A., 1993. Mining association rules between sets of items in large database. In: The ACM SIGMOD Conference, Washington DC, USA, pp. 207-216; Agrawal, R., Imielinksi, T., Swami, A., 1993. Mining association rules between sets of items in large database. In: The ACM SIGMOD Conference, Washington DC, USA, pp. 207-216 |
| [2] | Agrawal, R., Srikant, R., 1994. Fast algorithm for mining association rules. In: The International Conference on very Large Data Bases, pp. 487-499; Agrawal, R., Srikant, R., 1994. Fast algorithm for mining association rules. In: The International Conference on very Large Data Bases, pp. 487-499 |
| [3] | Agrawal, R., Srikant, R., 1995. Mining sequential patterns. In: The Eleventh IEEE International Conference on Data Engineering, pp. 3-14; Agrawal, R., Srikant, R., 1995. Mining sequential patterns. In: The Eleventh IEEE International Conference on Data Engineering, pp. 3-14 |
| [4] | Agrawal, R., Srikant, R., Vu, Q., 1997. Mining association rules with item constraints. In: The Third International Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, pp. 67-73; Agrawal, R., Srikant, R., Vu, Q., 1997. Mining association rules with item constraints. In: The Third International Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, pp. 67-73 |
| [5] | Cheung, D.W., Han, J., Ng, V.T., Wong, C.Y., 1996. Maintenance of discovered association rules in large databases: An incremental updating approach. In: The Twelfth IEEE International Conference on Data Engineering, pp. 106-114; Cheung, D.W., Han, J., Ng, V.T., Wong, C.Y., 1996. Maintenance of discovered association rules in large databases: An incremental updating approach. In: The Twelfth IEEE International Conference on Data Engineering, pp. 106-114 |
| [6] | Ezeife, C.I., 2002. Mining Incremental association rules with generalized FP-tree. In: Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, pp. 147-160; Ezeife, C.I., 2002. Mining Incremental association rules with generalized FP-tree. In: Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, pp. 147-160 · Zbl 1048.68578 |
| [7] | Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T., 1996. Mining optimized association rules for numeric attributes. In: The ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 182-191; Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T., 1996. Mining optimized association rules for numeric attributes. In: The ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 182-191 · Zbl 0943.68050 |
| [8] | Han, J., Fu, Y., 1995. Discovery of multiple-level association rules from large database. In: The Twenty-first International Conference on very Large Data Bases, Zurich, Switzerland, pp. 420-431; Han, J., Fu, Y., 1995. Discovery of multiple-level association rules from large database. In: The Twenty-first International Conference on very Large Data Bases, Zurich, Switzerland, pp. 420-431 |
| [9] | Han, J., Pei, J., Yin, Y., 2000. Mining frequent patterns without candidate generation. In: The 2000 ACM SIGMOD International Conference on Management of Data; Han, J., Pei, J., Yin, Y., 2000. Mining frequent patterns without candidate generation. In: The 2000 ACM SIGMOD International Conference on Management of Data |
| [10] | Hong, T.P., Lin, J.W., Wu, Y.L., 2006. A Fast updated frequent pattern tree. In: IEEE International Conference on Systems, Man, and Cybernetics; Hong, T.P., Lin, J.W., Wu, Y.L., 2006. A Fast updated frequent pattern tree. In: IEEE International Conference on Systems, Man, and Cybernetics |
| [11] | Mannila, H., Toivonen, H., Verkamo, A.I., 1994. Efficient algorithm for discovering association rules. In: The AAAI Workshop on Knowledge Discovery in Databases, pp. 181-192; Mannila, H., Toivonen, H., Verkamo, A.I., 1994. Efficient algorithm for discovering association rules. In: The AAAI Workshop on Knowledge Discovery in Databases, pp. 181-192 |
| [12] | Park, J. S.; Chen, M. S.; Yu, P. S., Using a hash-based method with transaction trimming for mining association rules, IEEE Transactions on Knowledge and Data Engineering, 9, 5, 812-825 (1997) |
| [13] | Qiu, Y., Lan, Y.J., Xie, Q.S., 2004. An improved algorithm of mining from FP-tree. In: Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, August, pp. 26-29; Qiu, Y., Lan, Y.J., Xie, Q.S., 2004. An improved algorithm of mining from FP-tree. In: Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, August, pp. 26-29 |
| [14] | Srikant, R., Agrawal, R., 1995. Mining generalized association rules. In: The Twenty-first International Conference on very Large Data Bases, Zurich, Switzerland, pp. 407-419; Srikant, R., Agrawal, R., 1995. Mining generalized association rules. In: The Twenty-first International Conference on very Large Data Bases, Zurich, Switzerland, pp. 407-419 |
| [15] | Srikant, R., Agrawal, R., 1996. Mining quantitative association rules in large relational tables. In: The 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Canada, pp. 1-12; Srikant, R., Agrawal, R., 1996. Mining quantitative association rules in large relational tables. In: The 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Canada, pp. 1-12 |
| [16] | Zaiane, O.R., Mohammed, E.H., 2003. COFI-tree mining: A new approach to pattern growth with reduced candidacy generation. In: IEEE International Conference on Data Mining; Zaiane, O.R., Mohammed, E.H., 2003. COFI-tree mining: A new approach to pattern growth with reduced candidacy generation. In: IEEE International Conference on Data Mining |
| [17] | Zheng, Z., Kohavi, R., Mason, L., 2001. Real world performance of association rule algorithms. In: The International Conference on Knowledge Discovery and Data Mining, pp. 401-406; Zheng, Z., Kohavi, R., Mason, L., 2001. Real world performance of association rule algorithms. In: The International Conference on Knowledge Discovery and Data Mining, pp. 401-406 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
