{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:26:12Z","timestamp":1760707572244},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>In the context of mining for frequent patterns using the standard levelwise algorithm, the following question arises: given the current level and the current set of frequent patterns, what is the maximal number of candidate patterns that can be generated on the next level? We answer this question by providing tight upper bounds, derived from a combinatorial result from the sixties by Kruskal and Katona. Our result is useful to secure existing algorithms from a combinatorial explosion of the number of candidate patterns.<\/jats:p>","DOI":"10.1145\/1071610.1071611","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"333-363","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Tight upper bounds on the number of candidate patterns"],"prefix":"10.1145","volume":"30","author":[{"given":"Floris","family":"Geerts","sequence":"first","affiliation":[{"name":"University of Edinburgh, Scotland, UK"}]},{"given":"Bart","family":"Goethals","sequence":"additional","affiliation":[{"name":"University of Helsinki"}]},{"given":"Jan Van Den","family":"Bussche","sequence":"additional","affiliation":[{"name":"Limburgs Universitair Centrum, Diepenbeek, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347114"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1693"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170072"},{"key":"e_1_2_1_4_1","unstructured":"Agrawal R. Mannila H. Srikant R. Toivonen H. and Verkamo A. 1996. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining U. Fayyad G. Piatetsky-Shapiro P. Smyth and R. Uthurusamy Eds. MIT Press 307--328.]]   Agrawal R. Mannila H. Srikant R. Toivonen H. and Verkamo A. 1996. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining U. Fayyad G. Piatetsky-Shapiro P. Smyth and R. Uthurusamy Eds. MIT Press 307--328.]]"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases, J. Bocca, M. Jarke, and C. Zaniolo, Eds. Morgan Kaufmann, 487--499","author":"Agrawal R.","unstructured":"Agrawal , R. and Srikant , R . 1994a. Fast algorithms for mining association rules . In Proceedings of the 20th International Conference on Very Large Data Bases, J. Bocca, M. Jarke, and C. Zaniolo, Eds. Morgan Kaufmann, 487--499 .]] Agrawal, R. and Srikant, R. 1994a. Fast algorithms for mining association rules. In Proceedings of the 20th International Conference on Very Large Data Bases, J. Bocca, M. Jarke, and C. Zaniolo, Eds. Morgan Kaufmann, 487--499.]]"},{"key":"e_1_2_1_6_1","unstructured":"Agrawal R. and Srikant R. 1994b. Fast algorithms for mining association rules. IBM Research Report RJ9839 IBM Alamaden Research Center San Jose California. June.]]  Agrawal R. and Srikant R. 1994b. Fast algorithms for mining association rules. IBM Research Report RJ9839 IBM Alamaden Research Center San Jose California. June.]]"},{"key":"e_1_2_1_7_1","unstructured":"Agrawal R. and Srikant R. 1994c. Quest Synthetic Data Generator. IBM Alamaden Research Center http:\/\/www.almaden.ibm.com\/software\/quest\/Resources\/index.shtml.]]  Agrawal R. and Srikant R. 1994c. Quest Synthetic Data Generator. IBM Alamaden Research Center http:\/\/www.almaden.ibm.com\/software\/quest\/Resources\/index.shtml.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276313"},{"key":"e_1_2_1_9_1","unstructured":"Blake C. and Merz C. 1998. UCI Repository of machine learning databases. University of California Irvine Dept. of Information and Computer Sciences http:\/\/www.ics.uci.edu\/~mlearn\/MLRepository.html.]]  Blake C. and Merz C. 1998. UCI Repository of machine learning databases. University of California Irvine Dept. of Information and Computer Sciences http:\/\/www.ics.uci.edu\/~mlearn\/MLRepository.html.]]"},{"key":"e_1_2_1_10_1","unstructured":"Bollob\u00e1s B. 1986. Combinatorics. Cambridge University Press.]]  Bollob\u00e1s B. 1986. Combinatorics. Cambridge University Press.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021571501451"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253325"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society, 443--452","author":"Burdick D.","unstructured":"Burdick , D. , Calimlim , M. , and Gehrke , J . 2001. MAFIA: A maximal frequent itemset algorithm for transactional databases . In Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society, 443--452 .]] Burdick, D., Calimlim, M., and Gehrke, J. 2001. MAFIA: A maximal frequent itemset algorithm for transactional databases. In Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society, 443--452.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90193-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.657870"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Workshop on Frequent Itemset Mining Implementations (FIMI-03)","author":"Goethals B.","year":"2003","unstructured":"Goethals , B. and Zaki , M. J. , Eds . 2003 . Proceedings of the Workshop on Frequent Itemset Mining Implementations (FIMI-03) , Melbourne Florida, USA , November 19, 2003 . CEUR Workshop Proceedings, vol. 90. http:\/\/CEUR-WS.org\/Vol-90\/.]] Goethals, B. and Zaki, M. J., Eds. 2003. Proceedings of the Workshop on Frequent Itemset Mining Implementations (FIMI-03), Melbourne Florida, USA, November 19, 2003. CEUR Workshop Proceedings, vol. 90. http:\/\/CEUR-WS.org\/Vol-90\/.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_18_1","unstructured":"Katona G. 1968. A theorem of finite sets. In Theory Of Graphs. Akad\u00e9mia Kiad\u00f3 187--207.]]  Katona G. 1968. A theorem of finite sets. In Theory Of Graphs. Akad\u00e9mia Kiad\u00f3 187--207.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380995.381033"},{"key":"e_1_2_1_20_1","volume-title":"Mathematical Optimization Techniques","author":"Kruskal J.","unstructured":"Kruskal , J. 1963. The number of simplices in a complex . In Mathematical Optimization Techniques . Univ. of California Press , 251--278.]] Kruskal, J. 1963. The number of simplices in a complex. In Mathematical Optimization Techniques. Univ. of California Press, 251--278.]]"},{"key":"e_1_2_1_21_1","volume-title":"Pincer-search: A new algorithm for discovering the maximum frequent set. In EDBT, H.-J","author":"Lin D.","year":"1998","unstructured":"Lin , D. and Kedem , Z . 1998 . Pincer-search: A new algorithm for discovering the maximum frequent set. In EDBT, H.-J . Schek, F. Saltor, I. Ramos, and G. Alonso, Eds. Lecture Notes in Computer Science, vol. 1377 . Springer , 105--119.]] Lin, D. and Kedem, Z. 1998. Pincer-search: A new algorithm for discovering the maximum frequent set. In EDBT, H.-J. Schek, F. Saltor, I. Ramos, and G. Alonso, Eds. Lecture Notes in Computer Science, vol. 1377. Springer, 105--119.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775081"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2002 IEEE International Conference on Data Mining, V. Kumar, S. Tsumoto, P. Yu, and N. Zhong, Eds. IEEE Computer Society","author":"Orlando S.","unstructured":"Orlando , S. , Palmerini , P. , Perego , R. , and Silvestri , F . 2002. Adaptive and resource-aware mining of frequent sets . In Proceedings of the 2002 IEEE International Conference on Data Mining, V. Kumar, S. Tsumoto, P. Yu, and N. Zhong, Eds. IEEE Computer Society , to appear.]] Orlando, S., Palmerini, P., Perego, R., and Silvestri, F. 2002. Adaptive and resource-aware mining of frequent sets. In Proceedings of the 2002 IEEE International Conference on Data Mining, V. Kumar, S. Tsumoto, P. Yu, and N. Zhong, Eds. IEEE Computer Society, to appear.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223813"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 7th International Conference on Database Theory, C. Beeri and P. Buneman, Eds. lncs","volume":"1540","author":"Pasquier N.","unstructured":"Pasquier , N. , Bastide , Y. , Taouil , R. , and Lakhal , L . 1999. Discovering frequent closed itemsets for association rules . In Proceedings of the 7th International Conference on Database Theory, C. Beeri and P. Buneman, Eds. lncs , vol. 1540 . Springer, 398--416.]] Pasquier, N., Bastide, Y., Taouil, R., and Lakhal, L. 1999. Discovering frequent closed itemsets for association rules. In Proceedings of the 7th International Conference on Database Theory, C. Beeri and P. Buneman, Eds. lncs, vol. 1540. Springer, 398--416.]]"},{"key":"e_1_2_1_26_1","volume-title":"ACM SIGMOD'00 Workshop on Research Issues in Data Mining and Knowledge Discovery.]]","author":"Pei J.","unstructured":"Pei , J. , Han , J. , and Mao , R . 2000. Closet: An efficient algorithm for mining frequent closed itemsets . ACM SIGMOD'00 Workshop on Research Issues in Data Mining and Knowledge Discovery.]] Pei, J., Han, J., and Mao, R. 2000. Closet: An efficient algorithm for mining frequent closed itemsets. ACM SIGMOD'00 Workshop on Research Issues in Data Mining and Knowledge Discovery.]]"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 21th International Conference on Very Large Data Bases, U. Dayal, P. Gray, and S. Nishio, Eds. Morgan Kaufmann, 432--444","author":"Savasere A.","unstructured":"Savasere , A. , Omiecinski , E. , and Navathe , S . 1995. An efficient algorithm for mining association rules in large databases . In Proceedings of the 21th International Conference on Very Large Data Bases, U. Dayal, P. Gray, and S. Nishio, Eds. Morgan Kaufmann, 432--444 .]] Savasere, A., Omiecinski, E., and Navathe, S. 1995. An efficient algorithm for mining association rules in large databases. In Proceedings of the 21th International Conference on Very Large Data Bases, U. Dayal, P. Gray, and S. Nishio, Eds. Morgan Kaufmann, 432--444.]]"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 22th International Conference on Very Large Data Bases, T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, Eds. Kaufmann, 134--145","author":"Toivonen H.","year":"1996","unstructured":"Toivonen , H. 1996 . Sampling large databases for association rules . In Proceedings of the 22th International Conference on Very Large Data Bases, T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, Eds. Kaufmann, 134--145 .]] Toivonen, H. 1996. Sampling large databases for association rules. In Proceedings of the 22th International Conference on Very Large Data Bases, T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, Eds. Kaufmann, 134--145.]]"},{"key":"e_1_2_1_29_1","volume-title":"-J","author":"Zaki M.","year":"2002","unstructured":"Zaki , M. and Hsiao , C . -J . 2002 . CHARM : An efficient algorithm for closed itemset mining. In Proceedings of the Second SIAM International Conference on Data Mining, R. Grossman, J. Han, V. Kumar, H. Mannila, and R. Motwani, Eds. SIAM.]] Zaki, M. and Hsiao, C.-J. 2002. CHARM: An efficient algorithm for closed itemset mining. In Proceedings of the Second SIAM International Conference on Data Mining, R. Grossman, J. Han, V. Kumar, H. Mannila, and R. Motwani, Eds. SIAM.]]"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, D. Heckerman, H. Mannila, and D. Pregibon, Eds. AAAI Press, 283--296","author":"Zaki M.","unstructured":"Zaki , M. , Parthasarathy , S. , Ogihara , M. , and Li , W . 1997. New algorithms for fast discovery of association rules . In Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, D. Heckerman, H. Mannila, and D. Pregibon, Eds. AAAI Press, 283--296 .]] Zaki, M., Parthasarathy, S., Ogihara, M., and Li, W. 1997. New algorithms for fast discovery of association rules. In Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, D. Heckerman, H. Mannila, and D. Pregibon, Eds. AAAI Press, 283--296.]]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502572"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071610.1071611","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:26:41Z","timestamp":1672244801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071610.1071611"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071610.1071611"],"URL":"https:\/\/doi.org\/10.1145\/1071610.1071611","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}