Efficient closed pattern mining in the presence of tough block constraints

Krishna Gade; Jianyong Wang; George Karypis

doi:10.1145/1014052.1014070

Efficient closed pattern mining in the presence of tough block constraints

Krishna Gade, Jianyong Wang, George Karypis

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

36 Scopus citations

Abstract

Various constrained frequent pattern mining problem formulations and associated algorithms have been developed that enable the user to specify various itemset-based constraints that better capture the underlying application requirements and characteristics. In this paper we introduce a new class of block constraints that determine the significance of an itemset pattern by considering the dense block that is formed by the pattern's items and its associated set of transactions. Block constraints provide a natural framework by which a number of important problems can be specified and make it possible to solve numerous problems on binary and real-valued datasets. However, developing computationally efficient algorithms to find these block constraints poses a number of challenges as unlike the different itemset-based constraints studied earlier, these block constraints are tough as they are neither anti-monotone, monotone, nor convertible. To overcome this problem, we introduce a new class of pruning methods that significantly reduce the overall search space and present a computationally efficient and scalable algorithm called CBMINER to find the closed itemsets that satisfy the block constraints.

Original language	English (US)
Title of host publication	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	138-147
Number of pages	10
ISBN (Print)	1581138881, 9781581138887
DOIs	https://doi.org/10.1145/1014052.1014070
State	Published - 2004
Event	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Seattle, WA, United States Duration: Aug 22 2004 → Aug 25 2004

Publication series

Name	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

Other	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Country/Territory	United States
City	Seattle, WA
Period	8/22/04 → 8/25/04

Keywords

Block constraint
Closed pattern
Tough constraint

Access

10.1145/1014052.1014070

OpenUrl availability

Full text

Cite this

Gade, K., Wang, J., & Karypis, G. (2004). Efficient closed pattern mining in the presence of tough block constraints. In KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 138-147). (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/1014052.1014070

Efficient closed pattern mining in the presence of tough block constraints. / Gade, Krishna; Wang, Jianyong; Karypis, George.
KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2004. p. 138-147 (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Gade, K, Wang, J & Karypis, G 2004, Efficient closed pattern mining in the presence of tough block constraints. in KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, pp. 138-147, KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, WA, United States, 8/22/04. https://doi.org/10.1145/1014052.1014070

Gade K, Wang J, Karypis G. Efficient closed pattern mining in the presence of tough block constraints. In KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2004. p. 138-147. (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/1014052.1014070

Gade, Krishna ; Wang, Jianyong ; Karypis, George. / Efficient closed pattern mining in the presence of tough block constraints. KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2004. pp. 138-147 (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{a3cbd66f6474481a89393c10f84f07c0,

title = "Efficient closed pattern mining in the presence of tough block constraints",

abstract = "Various constrained frequent pattern mining problem formulations and associated algorithms have been developed that enable the user to specify various itemset-based constraints that better capture the underlying application requirements and characteristics. In this paper we introduce a new class of block constraints that determine the significance of an itemset pattern by considering the dense block that is formed by the pattern's items and its associated set of transactions. Block constraints provide a natural framework by which a number of important problems can be specified and make it possible to solve numerous problems on binary and real-valued datasets. However, developing computationally efficient algorithms to find these block constraints poses a number of challenges as unlike the different itemset-based constraints studied earlier, these block constraints are tough as they are neither anti-monotone, monotone, nor convertible. To overcome this problem, we introduce a new class of pruning methods that significantly reduce the overall search space and present a computationally efficient and scalable algorithm called CBMINER to find the closed itemsets that satisfy the block constraints.",

keywords = "Block constraint, Closed pattern, Tough constraint",

author = "Krishna Gade and Jianyong Wang and George Karypis",

year = "2004",

doi = "10.1145/1014052.1014070",

language = "English (US)",

isbn = "1581138881",

series = "KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "138--147",

booktitle = "KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

note = "KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ; Conference date: 22-08-2004 Through 25-08-2004",

}

TY - GEN

T1 - Efficient closed pattern mining in the presence of tough block constraints

AU - Gade, Krishna

AU - Wang, Jianyong

AU - Karypis, George

PY - 2004

Y1 - 2004

N2 - Various constrained frequent pattern mining problem formulations and associated algorithms have been developed that enable the user to specify various itemset-based constraints that better capture the underlying application requirements and characteristics. In this paper we introduce a new class of block constraints that determine the significance of an itemset pattern by considering the dense block that is formed by the pattern's items and its associated set of transactions. Block constraints provide a natural framework by which a number of important problems can be specified and make it possible to solve numerous problems on binary and real-valued datasets. However, developing computationally efficient algorithms to find these block constraints poses a number of challenges as unlike the different itemset-based constraints studied earlier, these block constraints are tough as they are neither anti-monotone, monotone, nor convertible. To overcome this problem, we introduce a new class of pruning methods that significantly reduce the overall search space and present a computationally efficient and scalable algorithm called CBMINER to find the closed itemsets that satisfy the block constraints.

AB - Various constrained frequent pattern mining problem formulations and associated algorithms have been developed that enable the user to specify various itemset-based constraints that better capture the underlying application requirements and characteristics. In this paper we introduce a new class of block constraints that determine the significance of an itemset pattern by considering the dense block that is formed by the pattern's items and its associated set of transactions. Block constraints provide a natural framework by which a number of important problems can be specified and make it possible to solve numerous problems on binary and real-valued datasets. However, developing computationally efficient algorithms to find these block constraints poses a number of challenges as unlike the different itemset-based constraints studied earlier, these block constraints are tough as they are neither anti-monotone, monotone, nor convertible. To overcome this problem, we introduce a new class of pruning methods that significantly reduce the overall search space and present a computationally efficient and scalable algorithm called CBMINER to find the closed itemsets that satisfy the block constraints.

KW - Block constraint

KW - Closed pattern

KW - Tough constraint

UR - http://www.scopus.com/inward/record.url?scp=12344335874&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=12344335874&partnerID=8YFLogxK

U2 - 10.1145/1014052.1014070

DO - 10.1145/1014052.1014070

M3 - Conference contribution

AN - SCOPUS:12344335874

SN - 1581138881

SN - 9781581138887

T3 - KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 138

EP - 147

BT - KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Y2 - 22 August 2004 through 25 August 2004

ER -

Efficient closed pattern mining in the presence of tough block constraints

Abstract

Publication series

Other

Keywords

Access

OpenUrl availability

Other files and links

Cite this