A randomized approach for approximating the number of frequent sets

Mario Boley; Henrik Grosskreutz

doi:10.1109/ICDM.2008.85

A randomized approach for approximating the number of frequent sets

Mario Boley, Henrik Grosskreutz

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

16 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 language	English
Title of host publication	Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	43-52
Number of pages	10
ISBN (Print)	9780769535029
DOIs	https://doi.org/10.1109/ICDM.2008.85
Publication status	Published - 2008
Externally published	Yes
Event	IEEE International Conference on Data Mining 2008 - Pisa, Italy Duration: 15 Dec 2008 → 19 Dec 2008 Conference number: 8th https://ieeexplore.ieee.org/xpl/conhome/4781077/proceeding (Proceedings)

Conference

Conference	IEEE International Conference on Data Mining 2008
Abbreviated title	ICDM 2008
Country/Territory	Italy
City	Pisa
Period	15/12/08 → 19/12/08
Internet address	https://ieeexplore.ieee.org/xpl/conhome/4781077/proceeding (Proceedings)

Access to Document

10.1109/ICDM.2008.85

Cite this

@inproceedings{ef53b31d91364ebb83143346d52cf187,

title = "A randomized approach for approximating the number of frequent sets",

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.",

author = "Mario Boley and Henrik Grosskreutz",

year = "2008",

doi = "10.1109/ICDM.2008.85",

language = "English",

isbn = "9780769535029",

pages = "43--52",

booktitle = "Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

address = "United States of America",

note = "IEEE International Conference on Data Mining 2008, ICDM 2008 ; Conference date: 15-12-2008 Through 19-12-2008",

url = "https://ieeexplore.ieee.org/xpl/conhome/4781077/proceeding",

}

A randomized approach for approximating the number of frequent sets. / Boley, Mario; Grosskreutz, Henrik.
Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008. IEEE, Institute of Electrical and Electronics Engineers, 2008. p. 43-52 4781099.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A randomized approach for approximating the number of frequent sets

AU - Boley, Mario

AU - Grosskreutz, Henrik

N1 - Conference code: 8th

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/67049119060

U2 - 10.1109/ICDM.2008.85

DO - 10.1109/ICDM.2008.85

M3 - Conference Paper

AN - SCOPUS:67049119060

SN - 9780769535029

SP - 43

EP - 52

BT - Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008

PB - IEEE, Institute of Electrical and Electronics Engineers

T2 - IEEE International Conference on Data Mining 2008

Y2 - 15 December 2008 through 19 December 2008

ER -

A randomized approach for approximating the number of frequent sets

Abstract

Conference

Access to Document

Other files and links

Cite this