Statistical properties of transactional databases

Most of the complexity of common data mining tasks is due to the unknown amount of information contained in the data being mined. The more patterns and correlations are con-tained in such data, the more resources are needed to ex-tract them. This is confirmed by the fact that in general there is not a single best algorithm for a given data mining task on any possible kind of input dataset. Rather, in order to achieve good performances, strategies and optimizations have to be adopted according to the dataset specific char-acteristics. For example one typical distinction in transac-tional databases is between sparse and dense datasets. In this paper we consider Frequent Set Counting as a case study for data mining algorithms. We propose a statistical anal-ysis of the properties of transactional datasets that allows for a characterization of the dataset complexity. We show how such characterization can be used in many fields, from performance prediction to optimization. 1