An effective projection-reduction algorithm for mining long frequents

An effective projection-reduction algorithm for mining the long patterns frequent is presented. A new idea of top-down mining frequent items is adopted, and some new concepts such as transaction and items association information tables, key-items and reduction items, and projection DB are proposed. The algorithm presented is very effective for mining long frequents, and its validity is proved through analysis of computing complexity. Some examples of computation are given. The computing complexity of the algorithm is related to the average length of items reduction, the complexity approximates to 0.5 × M³N × 0(2^s × N´²) in the worst case, where S is the average length of items reduction under min-support given by user, N´ is the number of tuples in the database, N is the number of transactions in the database and M is the average length of item sets in the database. Using heuristic information for pruning useless candidate frequent itemsets improves the efficiency of the algorithm. The algorithm is very effective for mining long frequents, where S is very short and the computing complexity approaches polynomial time.