Estimating the number of frequent itemsets in a large database

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

• 1: Frequent itemset mining data repository. http://fimi.cs.helsinki.fi/data.
• 2: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 5: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 6: George Casella and Roger L. Berger. Statistical Inference, 2nd. Edition. DUXBURY Publishers, 2001.
• 7: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014064]
• 8: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 9: Floris Geerts , Bart Goethals , Jan Van Den Bussche, Tight upper bounds on the number of candidate patterns, ACM Transactions on Database Systems (TODS), v.30 n.2, p.333-363, June 2005 [doi>10.1145/1071610.1071611]
• 10: Karolien Geurts, Geert Wets, Tom Brijs, and Koen Vanhoof. Profiling high frequency accident locations using association rules. In Proceedings of the 82d Annual Transportation Research Board, 2003.
• 11: Dimitrios Gunopulos , Roni Khardon , Heikki Mannila , Sanjeev Saluja , Hannu Toivonen , Ram Sewak Sharma, Discovering all most specific sentences, ACM Transactions on Database Systems (TODS), v.28 n.2, p.140-174, June 2003 [doi>10.1145/777943.777945]
• 12: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 13: Donguk Kim , Alan Agresti, Nearly exact tests of conditional independence and marginal homogeneity for sparse contingency tables, Computational Statistics & Data Analysis, v.24 n.1, p.89-104, March 6, 1997 [doi>10.1016/S0167-9473(96)00038-2]
• 14: E. L. Lehmann and George Casella. Theory of Point Estimation, 2nd Edition. Springer-Verlag, 1998.
• 15: Wei Li , Ari Mozes, Computing frequent itemsets inside oracle 10G, Proceedings of the Thirtieth international conference on Very large data bases, p.1253-1256, August 31-September 03, 2004, Toronto, Canada
• 16: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 17: Francois Rioult , Arnaud Soulet, Average Number of Frequent (Closed) Patterns in Bernouilli and Markovian Databases, Proceedings of the Fifth IEEE International Conference on Data Mining, p.713-716, November 27-30, 2005 [doi>10.1109/ICDM.2005.31]
• 18: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 19: Takeaki Uno , Masashi Kiyomi , Hiroki Arimura, LCM ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.77-86, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1133905.1133916]
• 20: Craig Utley. Microsoft sql server 9.0 technical articles: Introduction to sql server 2005 data mining. http://technet.microsoft.com/en-us/library/ms345131.aspx.
• 21: Guizhen Yang, The complexity of mining maximal frequent itemsets and maximal frequent patterns, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014091]
• 22: Takeshi Yoshizawa , Iko Pramudiono , Masaru Kitsuregawa, SQL Based Association Rule Mining Using Commercial RDBMS (IBM DB2 UBD EEE), Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.301-306, September 04-06, 2000