DualMiner: A Dual-Pruning Algorithm for Itemsets with Constraints

Cristian Bucilǎ, Johannes Gehrke, Daniel Kifer, Walker White

Research output: Contribution to journalArticlepeer-review

52 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)241-272
Number of pages32
JournalData Mining and Knowledge Discovery
Issue number3
StatePublished - Jul 2003

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications

Cite this