DualMiner: A dual-pruning algorithm for itemsets with constraints

Cristian Bucila; Johannes Gehrke; Daniel Kifer; Walker White

DualMiner: A dual-pruning algorithm for itemsets with constraints

Cristian Bucila, Johannes Gehrke, Daniel Kifer, Walker White

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

Abstract

Constraint-based mining of itemsets for questions such as "find all frequent itemsets where the total price is at least $50" has received much attention recently. Two classes of constraints, monotone and antimonotone, have been identified as very useful. There are algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present the first algorithm (called DualMiner) that uses both monotone and antimonotone constraints to prune its search space. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.

Original language	English (US)
Title of host publication	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Editors	D. Hand, D. Keim, R. Ng
Pages	42-51
Number of pages	10
State	Published - 2002
Event	KDD - 2002 Proceedings of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Edmonton, Alta, Canada Duration: Jul 23 2002 → Jul 26 2002

Other

Other	KDD - 2002 Proceedings of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Country/Territory	Canada
City	Edmonton, Alta
Period	7/23/02 → 7/26/02

All Science Journal Classification (ASJC) codes

Software
Information Systems

Cite this

@inproceedings{dfdcd469bd8b4c649c002099429e2fa8,

title = "DualMiner: A dual-pruning algorithm for itemsets with constraints",

abstract = "Constraint-based mining of itemsets for questions such as {"}find all frequent itemsets where the total price is at least $50{"} has received much attention recently. Two classes of constraints, monotone and antimonotone, have been identified as very useful. There are algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present the first algorithm (called DualMiner) that uses both monotone and antimonotone constraints to prune its search space. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.",

author = "Cristian Bucila and Johannes Gehrke and Daniel Kifer and Walker White",

year = "2002",

language = "English (US)",

pages = "42--51",

editor = "D. Hand and D. Keim and R. Ng",

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

note = "KDD - 2002 Proceedings of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ; Conference date: 23-07-2002 Through 26-07-2002",

}

Bucila, C, Gehrke, J, Kifer, D & White, W 2002, DualMiner: A dual-pruning algorithm for itemsets with constraints. in D Hand, D Keim & R Ng (eds), Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 42-51, KDD - 2002 Proceedings of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alta, Canada, 7/23/02.

TY - GEN

T1 - DualMiner

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

AU - Bucila, Cristian

AU - Gehrke, Johannes

AU - Kifer, Daniel

AU - White, Walker

PY - 2002

Y1 - 2002

N2 - Constraint-based mining of itemsets for questions such as "find all frequent itemsets where the total price is at least $50" has received much attention recently. Two classes of constraints, monotone and antimonotone, have been identified as very useful. There are algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present the first algorithm (called DualMiner) that uses both monotone and antimonotone constraints to prune its search space. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.

AB - Constraint-based mining of itemsets for questions such as "find all frequent itemsets where the total price is at least $50" has received much attention recently. Two classes of constraints, monotone and antimonotone, have been identified as very useful. There are algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present the first algorithm (called DualMiner) that uses both monotone and antimonotone constraints to prune its search space. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.

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

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

M3 - Conference contribution

AN - SCOPUS:0242625292

SP - 42

EP - 51

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

A2 - Hand, D.

A2 - Keim, D.

A2 - Ng, R.

Y2 - 23 July 2002 through 26 July 2002

ER -

DualMiner: A dual-pruning algorithm for itemsets with constraints

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this