Pushing convertible constraints in frequent itemset mining

Jian Pei, Jiawei Han, Laks V.S. Lakshmanan

Research output: Contribution to journalArticle

Abstract

Recent work has highlighted the importance of the constraint-based mining paradigm in the context of frequent itemsets, associations, correlations, sequential patterns, and many other interesting patterns in large databases. Constraint pushing techniques have been developed for mining frequent patterns and associations with antimonotonic, monotonic, and succinct constraints. In this paper, we study constraints which cannot be handled with existing theory and techniques in frequent pattern mining. For example, avg(S)θv, median(S)θv, sum(S)θv (S can contain items of arbitrary values, θ ε {>, <, ≤, ≥} and v is a real number.) are customarily regarded as "tough" constraints in that they cannot be pushed inside an algorithm such as Apriori. We develop a notion of convertible constraints and systematically analyze, classify, and characterize this class. We also develop techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining. Results from our detailed experiments show the effectiveness of the techniques developed.

Original languageEnglish (US)
Pages (from-to)227-252
Number of pages26
JournalData Mining and Knowledge Discovery
Volume8
Issue number3
DOIs
StatePublished - May 1 2004

Keywords

  • Algorithm
  • Constraint
  • Convertible constraint
  • Frequent itemset mining
  • Pruning

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Pushing convertible constraints in frequent itemset mining'. Together they form a unique fingerprint.

  • Cite this