Progressive partition miner: An efficient algorithm for mining general temporal association rules
- 9 July 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 15 (4), 1004-1017
- https://doi.org/10.1109/tkde.2003.1209015
Abstract
We explore a new problem of mining general temporal association rules in publication databases. In essence, a publication database is a set of transactions where each transaction T is a set of items of which each item contains an individual exhibition period. The current model of association rule mining is not able to handle the publication database due to the following fundamental problems, i.e., 1) lack of consideration of the exhibition period of each individual item and 2) lack of an equitable support counting basis for each item. To remedy this, we propose an innovative algorithm progressive-partition-miner (abbreviated as PPM) to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database in light of exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset based on the intrinsic partitioning characteristics. Algorithm PPM is also designed to employ a filtering threshold in each partition to early prune out those cumulatively infrequent 2-itemsets. The feature that the number of candidate 2-itemsets generated by PPM is very close to the number of frequent 2-itemsets allows us to employ the scan reduction technique to effectively reduce the number of database scans. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by other competitive schemes that are directly extended from existing methods. The correctness of PPM is proven and some of its theoretical properties are derived. Sensitivity analysis of various parameters is conducted to provide many insights into Algorithm PPM.Keywords
This publication has 23 references indexed in Scilit:
- Pushing Convertible Constraints in Frequent Itemset MiningData Mining and Knowledge Discovery, 2004
- Mining association rules: anti-skew algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A survey of temporal knowledge discovery paradigms and methodsIEEE Transactions on Knowledge and Data Engineering, 2002
- An approach to discovering temporal association rulesPublished by Association for Computing Machinery (ACM) ,2000
- Efficient Mining of High Confidence Association Rules without Support ThresholdsLecture Notes in Computer Science, 1999
- Mining generalized association rulesFuture Generation Computer Systems, 1997
- Mining association rules with adjustable accuracyPublished by Association for Computing Machinery (ACM) ,1997
- Using a hash-based method with transaction trimming for mining association rulesIEEE Transactions on Knowledge and Data Engineering, 1997
- Data mining: an overview from a database perspectiveIEEE Transactions on Knowledge and Data Engineering, 1996
- Mining quantitative association rules in large relational tablesACM SIGMOD Record, 1996