{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:56:19Z","timestamp":1772121379987,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T00:00:00Z","timestamp":1659139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation NSF","doi-asserted-by":"crossref","award":["RI-1813444, IIS-2006765"],"award-info":[{"award-number":["RI-1813444, IIS-2006765"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DARPA\/ARFL","award":["FA8750"],"award-info":[{"award-number":["FA8750"]}]},{"name":"Italian Ministry of Education, University and Research","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}]},{"name":"SID 2020: RATED-X","award":["STARS 2018"],"award-info":[{"award-number":["STARS 2018"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\u201cI\u2019m an MC still as honest\u201d \u2013 Eminem, Rap God<\/jats:p>\n          <jats:p>\n            We present\n            <jats:sc>MCRapper<\/jats:sc>\n            , an algorithm for efficient computation of Monte-Carlo Empirical Rademacher Averages (MCERA) for families of functions exhibiting poset (e.g., lattice) structure, such as those that arise in many pattern mining tasks. The MCERA allows us to compute upper bounds to the maximum deviation of sample means from their expectations, thus it can be used to find both\n            <jats:italic>(1)<\/jats:italic>\n            statistically-significant functions (i.e., patterns) when the available data is seen as a sample from an unknown distribution, and\n            <jats:italic>(2)<\/jats:italic>\n            approximations of collections of high-expectation functions (e.g., frequent patterns) when the available data is a small sample from a large dataset. This flexibility offered by\n            <jats:sc>MCRapper<\/jats:sc>\n            is a big advantage over previously proposed solutions, which could only achieve one of the two.\n            <jats:sc>MCRapper<\/jats:sc>\n            uses upper bounds to the discrepancy of the functions to efficiently explore and prune the search space, a technique borrowed from pattern mining itself. To show the practical use of\n            <jats:sc>MCRapper<\/jats:sc>\n            , we employ it to develop an algorithm\n            <jats:sc>TFP-R<\/jats:sc>\n            for the task of True Frequent Pattern (TFP) mining, by appropriately computing approximations of the negative and positive borders of the collection of patterns of interest, which allow an effective pruning of the pattern space and the computation of strong bounds to the supremum deviation.\n            <jats:sc>TFP-R<\/jats:sc>\n            gives guarantees on the probability of including any false positives (precision) and exhibits higher statistical power (recall) than existing methods offering the same guarantees. We evaluate\n            <jats:sc>MCRapper<\/jats:sc>\n            and\n            <jats:sc>TFP-R<\/jats:sc>\n            and show that they outperform the state-of-the-art for their respective tasks.\n          <\/jats:p>","DOI":"10.1145\/3532187","type":"journal-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T16:28:02Z","timestamp":1650904082000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["MCRapper: Monte-Carlo Rademacher Averages for Poset Families and Approximate Pattern Mining"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6601-5526","authenticated-orcid":false,"given":"Leonardo","family":"Pellegrina","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Padova, Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1691-0282","authenticated-orcid":false,"given":"Cyrus","family":"Cousins","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2244-2320","authenticated-orcid":false,"given":"Fabio","family":"Vandin","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Padova, Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2523-4420","authenticated-orcid":false,"given":"Matteo","family":"Riondato","sequence":"additional","affiliation":[{"name":"Amherst College, Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,30]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170072"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655281"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_3_3_5_2","first-page":"463","article-title":"Rademacher and Gaussian complexities: Risk bounds and structural results","volume":"3","author":"Bartlett Peter L.","year":"2002","unstructured":"Peter L. Bartlett and Shahar Mendelson. 2002. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research 3, Nov (2002), 463\u2013482.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011429418057"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020500"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1631-073X(02)02292-6"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514927"},{"key":"e_1_3_3_10_2","first-page":"15123","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"33","author":"Cousins Cyrus","year":"2020","unstructured":"Cyrus Cousins and Matteo Riondato. 2020. Sharp uniform convergence bounds through empirical centralization. In Proceedings of the Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 15123\u201315132. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/ac457ba972fb63b7994befc83f774746-Paper.pdf."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467354"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSAA.2019.00021"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0501-6"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04921-8_1"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0590-x"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220359"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/int.4550070707"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1358-1_29"},{"key":"e_1_3_3_19_2","volume-title":"Proceedings of the 13th European Meeting on Cybernetics and Systems Research","author":"Mannila Heikki","year":"1996","unstructured":"Heikki Mannila and Hannu Toivonen. 1996. On an algorithm for finding all interesting sentences. In Proceedings of the 13th European Meeting on Cybernetics and Systems Research, Vol. II. Citeseer."},{"issue":"1","key":"e_1_3_3_20_2","first-page":"148","article-title":"On the method of bounded differences","volume":"141","author":"McDiarmid Colin","year":"1989","unstructured":"Colin McDiarmid. 1989. On the method of bounded differences. Surveys in Combinatorics 141, 1 (1989), 148\u2013188.","journal-title":"Surveys in Combinatorics"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2013.03.017"},{"key":"e_1_3_3_22_2","volume-title":"Rigorous and Efficient Algorithms for Significant and Approximate Pattern Mining","author":"Pellegrina Leonardo","year":"2021","unstructured":"Leonardo Pellegrina. 2021. Rigorous and Efficient Algorithms for Significant and Approximate Pattern Mining. Ph.D. Thesis. Universit\u00e1 degli Studi di Padova. Retrieved from http:\/\/www.dei.unipd.it\/pellegri\/thesis\/leonardo_pellegrina_tesi.pdf."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403267"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330978"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-020-00687-8"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629586"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783265"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.57"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219989"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385653"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13050123"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00057"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-019-01393-8"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.5"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1302233110"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673325"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00169"},{"key":"e_1_3_3_39_2","volume-title":"Statistical Learning Theory","author":"Vapnik Vladimir N.","year":"1998","unstructured":"Vladimir N. Vapnik. 1998. Statistical Learning Theory. Wiley."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3532187","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3532187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:42Z","timestamp":1750183782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3532187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,30]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3532187"],"URL":"https:\/\/doi.org\/10.1145\/3532187","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,30]]},"assertion":[{"value":"2021-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}