Under CopyrightBoley, MarioMarioBoleyGrosskreutz, HenrikHenrikGrosskreutz2022-03-0414.9.20102009https://publica.fraunhofer.de/handle/publica/21942510.1007/s10115-009-0212-4We 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 show that the algorithm still has the desired accuracy on several real-world datasets when its running time is capped polynomially.en005300journal article