Mining compressed frequent-pattern sets

Dong Xin, Jiawei Han, Xifeng Yan, Hong Cheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A major challenge in frequent-pattern mining is the sheer size of its mining results. In many cases, a high min_sup threshold may discover only commonsense patterns but a low one may generate an explosive number of output patterns, which severely restricts its usage. In this paper, we study the problem of compressing frequent-pattern sets. Typically, frequent patterns can be clustered with a tightness measure δ (called δ-cluster), and a representative pattern can be selected for each cluster. Unfortunately, finding a minimum set of representative patterns is NP-Hard. We develop two greedy methods, RP global 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[11], 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)
Title of host publicationVLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases
Pages709-720
Number of pages12
StatePublished - 2005
EventVLDB 2005 - 31st International Conference on Very Large Data Bases - Trondheim, Norway
Duration: Aug 30 2005Sep 2 2005

Publication series

NameVLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases
Volume2

Other

OtherVLDB 2005 - 31st International Conference on Very Large Data Bases
Country/TerritoryNorway
CityTrondheim
Period8/30/059/2/05

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Mining compressed frequent-pattern sets'. Together they form a unique fingerprint.

Cite this