Tight upper bounds on the number of candidate patterns

被引：14
作者：
Geerts, F
Goethals, B
Van den Bussche, J
机构：
[1] Univ Edinburgh, Sch Informat, Lab Fdn Comp Sci, Edinburgh EH8 9LE, Midlothian, Scotland
[2] Univ Helsinki, FIN-00014 Helsinki, Finland
[3] Limburgs Univ Ctr, Dept WNI, B-3590 Diepenbeek, Belgium
来源：
ACM TRANSACTIONS ON DATABASE SYSTEMS | 2005年 / 30卷 / 02期
关键词：
algorithms; performance; theory; data mining; frequent patterns; upper bounds;
D O I：
10.1145/1071610.1071611
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：333 / 363
页数：31
相关论文
共 31 条
[1]  
Agarwal R. C., 2000, Proceedings. KDD-2000. Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, P108, DOI 10.1145/347090.347114
[2]   A tree projection algorithm for generation of frequent item sets [J].
Agarwal, RC ;
Aggarwal, CC ;
Prasad, VVV .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2001, 61 (03) :350-371
[3]  
Agrawal R., 1993, SIGMOD Record, V22, P207, DOI 10.1145/170036.170072
[4]  
AGRAWAL R, 1994, RJ9839 IBM AL RES CT
[5]  
Agrawal R, 1994, P 20 INT C VER LARG, V1215, P487
[6]  
Agrawal Rakesh, 1994, Quest Synthetic Data Generator
[7]  
[Anonymous], 1996, Advances in Knowledge Discovery and Data Mining, DOI DOI 10.1007/978-3-319-31750-2.
[8]  
[Anonymous], 2002, P 8 ACM SIGKDD INT C, DOI DOI 10.1145/775047.775081
[9]  
[Anonymous], CEUR WORKSHOP P
[10]  
[Anonymous], P INT C VER LARG DAT
1234