TY - JOUR
T1 - DualMiner
T2 - A Dual-Pruning Algorithm for Itemsets with Constraints
AU - Bucilǎ, Cristian
AU - Gehrke, Johannes
AU - Kifer, Daniel
AU - White, Walker
N1 - Funding Information:
This work was supported by NSF Grants IIS-0084762 and IIS-0121175, and by gifts from Microsoft and Intel. Walker White was also supported by the Cornell Intelligent Systems Institute, and Dan Kifer was also supported by an NSF Fellowship. We thank the anonymous reviewers for helpful comments.
PY - 2003/7
Y1 - 2003/7
N2 - Recently, constraint-based raining of itemsets for questions like "find all frequent itemsets whose total price is at least $50" has attracted much attention. Two classes of constraints, monotone and antimonotone, have been very useful in this area. There exist 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 DualMiner, the first algorithm that efficiently prunes its search space using both monotone and antimonotone constraints. 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 - Recently, constraint-based raining of itemsets for questions like "find all frequent itemsets whose total price is at least $50" has attracted much attention. Two classes of constraints, monotone and antimonotone, have been very useful in this area. There exist 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 DualMiner, the first algorithm that efficiently prunes its search space using both monotone and antimonotone constraints. 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=0037865635&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037865635&partnerID=8YFLogxK
U2 - 10.1023/A:1024076020895
DO - 10.1023/A:1024076020895
M3 - Article
AN - SCOPUS:0037865635
SN - 1384-5810
VL - 7
SP - 241
EP - 272
JO - Data Mining and Knowledge Discovery
JF - Data Mining and Knowledge Discovery
IS - 3
ER -