Estimating the number of frequent itemsets in a large database

Ruoming Jin, Scott McCallen, Yuri Breitbart, Dave Fuhry, Dong Wang

2009 · 10 citations · 20 references

DOIFull text

Open access

Concepts

Abstract

Estimating the number of frequent itemsets for minimal support α in a large dataset is of great interest from both theoretical and practical perspectives. However, finding not only the number of frequent itemsets, but even the number of maximal frequent itemsets, is #P-complete. In this study, we provide a theoretical investigation on the sampling estimator. We discover and prove several fundamental but also rather surprising properties of the sampling estimator. We also propose a novel algorithm to estimate the number of frequent itemsets without using sampling. Our detailed experimental results have shown the accuracy and efficiency of our proposed approach.

References

20