{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T15:42:48Z","timestamp":1780760568262,"version":"3.54.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PON Project \u201cInMoto \u2014 Information Mobility for Tourism\u201d)"},{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009877","name":"Calabria Region","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009877","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            <jats:italic>Inverse frequent set mining<\/jats:italic>\n            (IFM) is the problem of computing a transaction database D satisfying given support constraints for some itemsets, which are typically the frequent ones. This article proposes a new formulation of IFM, called IFM\n            <jats:sub>I<\/jats:sub>\n            (IFM\n            <jats:italic>with infrequency constraints<\/jats:italic>\n            ), where the itemsets that are not listed as frequent are constrained to be infrequent; that is, they must have a support less than or equal to a specified unique threshold. An instance of IFM\n            <jats:sub>I<\/jats:sub>\n            can be seen as an instance of the original IFM by making explicit the infrequency constraints for the minimal infrequent itemsets, corresponding to the so-called negative generator border defined in the literature. The complexity increase from PSPACE (complexity of IFM) to NEXP (complexity of IFM\n            <jats:sub>I<\/jats:sub>\n            ) is caused by the cardinality of the negative generator border, which can be exponential in the original input size. Therefore, the article introduces a specific problem parameter \u03ba that computes an upper bound to this cardinality using a hypergraph interpretation for which minimal infrequent itemsets correspond to minimal transversals. By fixing a constant\n            <jats:italic>k<\/jats:italic>\n            , the article formulates a\n            <jats:italic>k<\/jats:italic>\n            -bounded definition of the problem, called\n            <jats:italic>k<\/jats:italic>\n            -IFM\n            <jats:sub>I<\/jats:sub>\n            , that collects all instances for which the value of the parameter \u03ba is less than or equal to\n            <jats:italic>k<\/jats:italic>\n            \u2014its complexity is in PSPACE as for IFM. The bounded problem is encoded as an integer linear program with a large number of variables (actually exponential w.r.t. the number of constraints), which is thereafter approximated by relaxing integer constraints\u2014the decision problem of solving the linear program is proven to be in NP. In order to solve the linear program, a column generation technique is used that is a variation of the simplex method designed to solve large-scale linear programs, in particular with a huge number of variables. The method at each step requires the solution of an auxiliary integer linear program, which is proven to be NP hard in this case and for which a greedy heuristic is presented. The resulting overall column generation solution algorithm enjoys very good scaling as evidenced by the intensive experimentation, thereby paving the way for its application in real-life scenarios.\n          <\/jats:p>","DOI":"10.1145\/2541268.2541271","type":"journal-article","created":{"date-parts":[[2014,1,6]],"date-time":"2014-01-06T20:42:39Z","timestamp":1389040959000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Solving inverse frequent itemset mining with infrequency constraints via large-scale linear programs"],"prefix":"10.1145","volume":"7","author":[{"given":"Antonella","family":"Guzzo","sequence":"first","affiliation":[{"name":"University of Calabria, Rende (CS), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luigi","family":"Moccia","sequence":"additional","affiliation":[{"name":"Consiglio Nazionale delle Ricerche - Istituto di Calcolo e Reti ad Alte Prestazioni, Rende (CS), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Domenico","family":"Sacc\u00e0","sequence":"additional","affiliation":[{"name":"University of Calabria, Rende (CS), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edoardo","family":"Serra","sequence":"additional","affiliation":[{"name":"University of Calabria, Rende (CS), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,12,25]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375602"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335438"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/380995.381017"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.42"},{"key":"e_1_2_2_5_1","unstructured":"Berge C. 1973. Graphs and Hypergraphs. North-Holland Pub. Co. Amsterdam The Netherlands.  Berge C. 1973. Graphs and Hypergraphs. North-Holland Pub. Co. Amsterdam The Netherlands."},{"key":"e_1_2_2_6_1","unstructured":"Bertsimas D. and Tsitsiklis J. N. 1997. Introduction to Linear Optimization. Athena Scientific Belmont MA.   Bertsimas D. and Tsitsiklis J. N. 1997. Introduction to Linear Optimization. Athena Scientific Belmont MA."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024605820527"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375604"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055580"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-007-0060-1"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.11.003"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Springer","author":"Calders T.","unstructured":"Calders , T. and Goethals , B . 2003. Minimal k-free representations of frequent sets . In Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Springer , Berlin, 71--82. Calders, T. and Goethals, B. 2003. Minimal k-free representations of frequent sets. In Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Springer, Berlin, 71--82."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0054-6"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11615576_4"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/248603.248616"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11527503_89"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the IEEE ICDM Workshop on Privacy and Security Aspects of Data Mining. IEEE Computer Society","author":"Chen X.","unstructured":"Chen , X. , Orlowska , M. , and Li , X . 2004. A new framework of privacy preserving data sharing . In Proceedings of the IEEE ICDM Workshop on Privacy and Security Aspects of Data Mining. IEEE Computer Society , Washington, DC, 47--56. Chen, X., Orlowska, M., and Li, X. 2004. A new framework of privacy preserving data sharing. In Proceedings of the IEEE ICDM Workshop on Privacy and Security Aspects of Data Mining. IEEE Computer Society, Washington, DC, 47--56."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_10"},{"key":"e_1_2_2_19_1","unstructured":"Dantzig G. B. and Thapa M. N. 2006. Linear Programming 2: Theory and Extensions. Springer-Verlag Berlin.  Dantzig G. B. and Thapa M. N. 2006. Linear Programming 2: Theory and Extensions. Springer-Verlag Berlin."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Desaulniers G. Desrosiers J. and Solomon M. M. 2005. Column Generation. Springer Berlin.  Desaulniers G. Desrosiers J. and Solomon M. M. 2005. Column Generation. Springer Berlin.","DOI":"10.1007\/b135457"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag Berlin.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag Berlin.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250299"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG\u201911)","author":"Elbassioni K. M.","unstructured":"Elbassioni , K. M. , Rauf , I. , and Ray , S . 2011. Enumerating minimal transversals of geometric hypergraphs . In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG\u201911) . Toronto, Ontario, Canada. Elbassioni, K. M., Rauf, I., and Ray, S. 2011. Enumerating minimal transversals of geometric hypergraphs. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG\u201911). Toronto, Ontario, Canada."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775080"},{"key":"e_1_2_2_27_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag Berlin.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag Berlin."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0062"},{"key":"e_1_2_2_29_1","unstructured":"Golfarelli M. and Rizzi S. 2009. Data Warehouse Design: Modern Principles and Methodologies. McGraw Hill New York.   Golfarelli M. and Rizzi S. 2009. Data Warehouse Design: Modern Principles and Methodologies. McGraw Hill New York."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2463673"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263684"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11788911_13"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.123"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0059-1"},{"key":"e_1_2_2_35_1","volume-title":"Data Mining: Concepts and Techniques","author":"Han J.","year":"2006","unstructured":"Han , J. and Kamber , M . 2006 . Data Mining: Concepts and Techniques 2 nd Ed., Morgan Kaufmann, San Francisco , CA. Han, J. and Kamber, M. 2006. Data Mining: Concepts and Techniques 2nd Ed., Morgan Kaufmann, San Francisco, CA.","edition":"2"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081969"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_2_38_1","unstructured":"KDDCUP2000. 2000. Retrieved April 16 from http:\/\/www.ecn.purdue.edu\/KDDCUP.  KDDCUP2000. 2000. Retrieved April 16 from http:\/\/www.ecn.purdue.edu\/KDDCUP."},{"key":"e_1_2_2_39_1","first-page":"1093","article-title":"A polynomial algorithm for linear programming","volume":"244","author":"Khachian L. G.","year":"1979","unstructured":"Khachian , L. G. 1979 . A polynomial algorithm for linear programming . Dokl. Akad. Nauk SSSR 244 , 5, 1093 -- 1096 . English translation in Soviet Math. Dokl. 20, 191--194, 1979. Khachian, L. G. 1979. A polynomial algorithm for linear programming. Dokl. Akad. Nauk SSSR 244, 5, 1093--1096. English translation in Soviet Math. Dokl. 20, 191--194, 1979.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.657874"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD\u201902)","author":"Kryszkiewicz M.","unstructured":"Kryszkiewicz , M. and Gajek , M . 2002. Concise representation of frequent patterns based on generalized disjunction-free generators . In Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD\u201902) . Springer-Verlag, London, UK, 159--171. Kryszkiewicz, M. and Gajek, M. 2002. Concise representation of frequent patterns based on generalized disjunction-free generators. In Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD\u201902). Springer-Verlag, London, UK, 159--171."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0111-5"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2007.06.011"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796218281"},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of 2nd Workshop on Privacy Preserving Data Mining (PPDM\u201903)","author":"Mielikainen T.","year":"2003","unstructured":"Mielikainen , T. 2003 . On inverse frequent set mining . In Proceedings of 2nd Workshop on Privacy Preserving Data Mining (PPDM\u201903) . IEEE Computer Society, Washington, DC, 18--23. Mielikainen, T. 2003. On inverse frequent set mining. In Proceedings of 2nd Workshop on Privacy Preserving Data Mining (PPDM\u201903). IEEE Computer Society, Washington, DC, 18--23."},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the 17th Australasian Database Conference -","volume":"49","author":"Natwichai J.","unstructured":"Natwichai , J. , Li , X. , and Orlowska , M. E . 2006. A reconstruction-based algorithm for classification rules hiding . In Proceedings of the 17th Australasian Database Conference - Volume 49 (ADC\u201906). Australian Computer Society, Inc., Darlinghurst, Australia, 49--58. Natwichai, J., Li, X., and Orlowska, M. E. 2006. A reconstruction-based algorithm for classification rules hiding. In Proceedings of the 17th Australasian Database Conference - Volume 49 (ADC\u201906). Australian Computer Society, Inc., Darlinghurst, Australia, 49--58."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952071"},{"key":"e_1_2_2_48_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison-Wesley , Reading, MA . Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, MA."},{"key":"e_1_2_2_49_1","volume-title":"Proceedings of the 7th International Conference on Database Theory (ICDT\u201999)","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 (ICDT\u201999) . Springer-Verlag, London, UK, 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 (ICDT\u201999). Springer-Verlag, London, UK, 398--416."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773181"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/IDEAS.2005.22"},{"key":"e_1_2_2_52_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB\u201902)","author":"Rizvi S. J.","unstructured":"Rizvi , S. J. and Haritsa , J. R . 2002. Maintaining data privacy in association rule mining . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB\u201902) . VLDB Endowment, 682--693. Rizvi, S. J. and Haritsa, J. R. 2002. Maintaining data privacy in association rule mining. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB\u201902). VLDB Endowment, 682--693."},{"key":"e_1_2_2_53_1","unstructured":"Sacc\u00e0 D. and Serra E. 2013. Number of minimal hypergraph transversals and complexity of IFM with infrequency: High in theory but often not so much in practice&excl; Website. Online Preliminary Paper from http:\/\/sacca.deis.unical.it\/&num;view=object&format=object&id=1490\/gid=160.  Sacc\u00e0 D. and Serra E. 2013. Number of minimal hypergraph transversals and complexity of IFM with infrequency: High in theory but often not so much in practice&excl; Website. Online Preliminary Paper from http:\/\/sacca.deis.unical.it\/&num;view=object&format=object&id=1490\/gid=160."},{"key":"e_1_2_2_54_1","unstructured":"Sacc\u00e0 D. Serra E. and Gaudioso M. 2012a. Succinct linear programming: Complexity algorithms and applications. Website. Online Preliminary Paper from http:\/\/sacca.deis.unical.it\/&num;view=object&format=object&id=1056\/gid=160.  Sacc\u00e0 D. Serra E. and Gaudioso M. 2012a. Succinct linear programming: Complexity algorithms and applications. Website. Online Preliminary Paper from http:\/\/sacca.deis.unical.it\/&num;view=object&format=object&id=1056\/gid=160."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28472-4_20"},{"key":"e_1_2_2_56_1","unstructured":"Sacc\u00e0 D. Serra E. and Guzzo A. 2013. Extending inverse frequent itemsets mining to generate realistic datasets: Complexity accuracy and emerging applications. Website. Online Preliminary Paper from http:\/\/sacca.deis.unical.it\/&num;view=object&format=object&id=1145\/gid=160.  Sacc\u00e0 D. Serra E. and Guzzo A. 2013. Extending inverse frequent itemsets mining to generate realistic datasets: Complexity accuracy and emerging applications. Website. Online Preliminary Paper from http:\/\/sacca.deis.unical.it\/&num;view=object&format=object&id=1145\/gid=160."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1570256.1570371"},{"key":"e_1_2_2_58_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases (VLDB\u201900)","author":"Wang K.","unstructured":"Wang , K. , He , Y. , and Han , J . 2000. Mining frequent itemsets using support constraints . In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB\u201900) . Morgan Kaufmann Publishers Inc., San Francisco, CA, 43--52. Wang, K., He, Y., and Han, J. 2000. Mining frequent itemsets using support constraints. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB\u201900). Morgan Kaufmann Publishers Inc., San Francisco, CA, 43--52."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.27"},{"key":"e_1_2_2_60_1","volume-title":"Proceedings of SIAM International Conference on Data Mining (SDM'05)","author":"Wu X.","unstructured":"Wu , X. , Wu , Y. , Wang , Y. , and Li , Y . 2005. Privacy aware market basket data set generation: A feasible approach for inverse frequent set mining . In Proceedings of SIAM International Conference on Data Mining (SDM'05) . SIAM, Philadelphia, PA, 103--114. Wu, X., Wu, Y., Wang, Y., and Li, Y. 2005. Privacy aware market basket data set generation: A feasible approach for inverse frequent set mining. In Proceedings of SIAM International Conference on Data Mining (SDM'05). SIAM, Philadelphia, PA, 103--114."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502572"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541268.2541271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2541268.2541271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:35:01Z","timestamp":1750232101000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541268.2541271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2541268.2541271"],"URL":"https:\/\/doi.org\/10.1145\/2541268.2541271","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}