A tight upper bound on the number of candidate patterns

被引：15

作者：

Geerts, F ^{[1
]}

Goethals, B ^{[1
]}

Van den Bussche, J ^{[1
]}

机构：

[1] Limburgs Univ Ctr, Limburg, Belgium

来源：

2001 IEEE INTERNATIONAL CONFERENCE ON DATA MINING, PROCEEDINGS | 2001年

关键词：

D O I：

10.1109/ICDM.2001.989513

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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 tipper bound, derived from a combinatorial result front the sixties by, Kruskal and Katona. Our result is useful to reduce the number of database scans.

引用

页码：155 / 162

页数：8

共 50 条

[1] Tight upper bounds on the number of candidate patterns
Geerts, F
Goethals, B
Van den Bussche, J
ACM TRANSACTIONS ON DATABASE SYSTEMS, 2005, 30 (02): : 333 - 363
[2] The tight upper bound for the number of matchings of tricyclic graphs
Dolati, Ardeshir
Golalizadeh, Somayyeh
ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (01):
[3] A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
van Zuylen, Anke
Bieron, James
Schalekamp, Frans
Yu, Gexin
INFORMATION PROCESSING LETTERS, 2016, 116 (11) : 718 - 722
[4] A TIGHT UPPER BOUND FOR THE NUMBER OF INTERSECTIONS BETWEEN 2 RECTANGULAR PATHS
TEO, KH
TUAN, TC
BIT, 1991, 31 (04): : 598 - 606
[5] A tight upper bound on the number of non-zero weights of a constacyclic code
Zhang, Hanglong
Cao, Xiwang
FINITE FIELDS AND THEIR APPLICATIONS, 2024, 93
[6] A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs
Hasunuma, Toru
Ishii, Toshimasa
Ono, Hirotaka
Uno, Yushi
JOURNAL OF DISCRETE ALGORITHMS, 2012, 14 : 189 - 206
[7] Sum coloring and interval graphs: a tight upper bound for the minimum number of colors
Nicoloso, S
DISCRETE MATHEMATICS, 2004, 280 (1-3) : 251 - 257
[8] A Tight Upper Bound on the Number of Non-Zero Weights of a Cyclic Code
Chen, Bocong
Zhang, Guanghui
IEEE TRANSACTIONS ON INFORMATION THEORY, 2023, 69 (02) : 995 - 1004
[9] Bushiness and a tight worst-case upper bound on the search number of a simple polygon
Suzuki, I
Yamashita, M
Umemoto, H
Kameda, T
INFORMATION PROCESSING LETTERS, 1998, 66 (01) : 49 - 52
[10] Tight upper bound on discrete entropy
Nanyang Technological Univ, Singapore
IEEE Trans Inf Theory, 2 (775-778):

← 1 2 3 4 5 →