Tight upper bounds on the number of candidate patterns Floris Geerts, Bart Goethals, and Jan Van den Bussche   View Paper (PDF)   Return to June 2005, Volume 30, Issue 2 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 tight upper bounds, derived from a combinatorial result from the sixties by Kruskal and Katona. Our result is useful to secure existing algorithms from a combinatorial explosion of the number of candidate patterns. ©2006 Association for Computing Machinery