Maintenance of fast updated frequent pattern trees for record deletion

Tzung-Pei Hong, Chun-Wei Lin and Yu-Lung Wu

Computational Statistics & Data Analysis, 2009, vol. 53, issue 7, 2485-2499

Abstract: 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 etal. 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.

Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167-9473(09)00027-9
Full text for ScienceDirect subscribers only.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:csdana:v:53:y:2009:i:7:p:2485-2499

Access Statistics for this article

Computational Statistics & Data Analysis is currently edited by S.P. Azen

More articles in Computational Statistics & Data Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().