An effective projection-reduction algorithm for mining long frequents

An effective Projection-reduction Algorithm for mining long patterns frequent is presented. A new ideal of top-down ning frequent items is adopted, and some of new conceptions such as transaction and items association information tables, key-items and reduction items, projection DB. etc. are proposed, The algorithm presented is very effective for mining long frequents, the validity of proposed algorithms is proved through analysis computing complexity, Some examples of computation are given also. The computing complexity of the algorithm has relation to the average length of items reduction, the complexity approximates to 0.5xM(3)N xO(2(S)xN'(2)) in worst of case. here, 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 numbers of the transaction in databases, M is the average length of item sets in databases. On the side, using heuristic information for pruning useless candidate frequent itemsets, the efficiency of algorithm is improved notably. It is very effective for mining long frequent, since S is very short for long pattern frequent, the computing complexity approach to polynomial time.