A randomized approach for approximating the number of frequent sets

Mario Boley, Henrik Grosskreutz

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

15 Citations (Scopus)

Abstract

We investigate the problem of counting the number of frequent (item)sets-a problem known to be intractable in terms of an exact polynomial time computation. In this paper, we show that it is in general also hard to approximate. Subsequently, a randomized counting algorithm is developed using the Markov chain Monte Carlo method. While for general inputs an exponential running time is needed in order to guarantee a certain approximation bound, we empirically show that the algorithm still has the desired accuracy on real-world datasets when its running time is capped polynomially.

Original languageEnglish
Title of host publicationProceedings - 8th IEEE International Conference on Data Mining, ICDM 2008
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages43-52
Number of pages10
ISBN (Print)9780769535029
DOIs
Publication statusPublished - 2008
Externally publishedYes
EventIEEE International Conference on Data Mining 2008 - Pisa, Italy
Duration: 15 Dec 200819 Dec 2008
Conference number: 8th
https://ieeexplore.ieee.org/xpl/conhome/4781077/proceeding (Proceedings)

Conference

ConferenceIEEE International Conference on Data Mining 2008
Abbreviated titleICDM 2008
Country/TerritoryItaly
CityPisa
Period15/12/0819/12/08
Internet address

Cite this