A Tight Upper Bound on the Number of Candidate Patterns

2001/12/07 by Floris Geerts, Geerts, Floris, Bart Goethals +3
Computer Science · #Advanced Database Systems and Queries #Data Mining Algorithms and Applications #Rough Sets and Fuzzy Logic #cs.AI #cs.DB

paper · pdf · doi:10.48550/arxiv.cs/0112007

arxiv created 2002/11/30 · arxiv updated 2009/11/30

Abstract

In the context of mining for frequent patterns using the standard levelwise algorithm, the following question arises: given the current level and the current set of frequent patterns, what is the maximal number of candidate patterns that can be generated on the next level? We answer this question by providing a tight upper bound, derived from a combinatorial result from the sixties by Kruskal and Katona. Our result is useful to reduce the number of database scans.

Related

• Reductions for Frequency-Based Data Mining Problems
• Mining Top-k Approximate Frequent Patterns
• Mining frequent patterns without candidate generation
• Fast and Memory-Efficient Significant Pattern Mining via Permutation\n Testing
• DESQ: Frequent Sequence Mining with Subsequence Constraints