On compressing frequent patterns

Dong Xin, Jiawei Han, Xifeng Yan, Hong Cheng

Research output: Contribution to journalArticlepeer-review


A major challenge in frequent-pattern mining is the sheer size of its mining results. To compress the frequent patterns, we propose to cluster frequent patterns with a tightness measure δ (called δ-cluster), and select a representative pattern for each cluster. The problem of finding a minimum set of representative patterns is shown NP-Hard. We develop two greedy methods, RPglobal and RPlocal. The former has the guaranteed compression bound but higher computational complexity. The latter sacrifices the theoretical bounds but is far more efficient. Our performance study shows that the compression quality using RPlocal is very close to RPglobal, and both can reduce the number of closed frequent patterns by almost two orders of magnitude. Furthermore, RPlocal mines even faster than FPClose [G. Grahne, J. Zhu, Efficiently using prefix-trees in mining frequent itemsets, in: Proc. IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI'03)], a very fast closed frequent-pattern mining method. We also show that RPglobal and RPlocal can be combined together to balance the quality and efficiency.

Original languageEnglish (US)
Pages (from-to)5-29
Number of pages25
JournalData and Knowledge Engineering
Issue number1
StatePublished - Jan 2007


  • Data mining
  • Frequent pattern mining

ASJC Scopus subject areas

  • Information Systems and Management


Dive into the research topics of 'On compressing frequent patterns'. Together they form a unique fingerprint.

Cite this