{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:55:07Z","timestamp":1761897307337,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20174LF3T8","Departments of Excellence (Law 232\/2016)"],"award-info":[{"award-number":["20174LF3T8","Departments of Excellence (Law 232\/2016)"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"publisher","award":["STARS2017"],"award-info":[{"award-number":["STARS2017"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Sequential pattern mining is a fundamental data mining task with application in several domains. We study two variants of this task\u2014the first is the extraction of frequent sequential patterns, whose frequency in a dataset of sequential transactions is higher than a user-provided threshold; the second is the mining of true frequent sequential patterns, which appear with probability above a user-defined threshold in transactions drawn from the generative process underlying the data. We present the first sampling-based algorithm to mine, with high confidence, a rigorous approximation of the frequent sequential patterns from massive datasets. We also present the first algorithms to mine approximations of the true frequent sequential patterns with rigorous guarantees on the quality of the output. Our algorithms are based on novel applications of Vapnik-Chervonenkis dimension and Rademacher complexity, advanced tools from statistical learning theory, to sequential pattern mining. Our extensive experimental evaluation shows that our algorithms provide high-quality approximations for both problems we consider.<\/jats:p>","DOI":"10.3390\/a13050123","type":"journal-article","created":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T11:34:14Z","timestamp":1589801654000},"page":"123","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Mining Sequential Patterns with VC-Dimension and Rademacher Complexity"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2013-0251","authenticated-orcid":false,"given":"Diego","family":"Santoro","sequence":"first","affiliation":[{"name":"Department of Information Engineering, University of Padova, 35131 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5676-0269","authenticated-orcid":false,"given":"Andrea","family":"Tonon","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Padova, 35131 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2244-2320","authenticated-orcid":false,"given":"Fabio","family":"Vandin","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Padova, 35131 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,5,18]]},"reference":[{"key":"ref_1","unstructured":"Agrawal, R., and Srikant, R. (1995, January 6\u201310). Mining sequential patterns. Proceedings of the Eleventh International Conference on Data Engineering, Taipei, China."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Vovk, V., Papadopoulos, H., and Gammerman, A. (2015). On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Measures of Complexity, Springer.","DOI":"10.1007\/978-3-319-21852-6"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1051\/ps:2005018","article-title":"Theory of classification: A survey of some recent advances","volume":"9","author":"Boucheron","year":"2005","journal-title":"ESAIM Probab. Stat."},{"key":"ref_4","first-page":"20","article-title":"Efficient discovery of association rules and frequent itemsets through sampling with tight performance guarantees","volume":"8","author":"Riondato","year":"2014","journal-title":"ACM Trans. Knowl. Discov. D"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Riondato, M., and Upfal, E. (2015, January 22\u201327). Mining frequent itemsets through progressive sampling with rademacher averages. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/2783258.2783265"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ra\u00efssi, C., and Poncelet, P. (2007, January 28\u201331). Sampling for sequential pattern mining: From static databases to data streams. Proceedings of the Seventh IEEE International Conference on Data Mining (ICDM 2007), Omaha, NE, USA.","DOI":"10.1109\/ICDM.2007.82"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Riondato, M., and Vandin, F. (2014, January 28). Finding the true frequent itemsets. Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia, PA, USA.","DOI":"10.1137\/1.9781611973440.57"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1007\/s10115-019-01393-8","article-title":"ProSecCo: Progressive sequence mining with convergence guarantees","volume":"62","author":"Riondato","year":"2020","journal-title":"Knowl. Inf. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Srikant, R., and Agrawal, R. (1996). Mining sequential patterns: Generalizations and performance improvements. Advances in Database Technology\u2013EDBT \u201996, Proceedings of the International Conference on Extending Database Technology, Avignon, France, 25\u201329 March 1996, Springer.","DOI":"10.1007\/BFb0014140"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1424","DOI":"10.1109\/TKDE.2004.77","article-title":"Mining sequential patterns by pattern-growth: The prefixspan approach","volume":"16","author":"Pei","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1109\/TKDE.2007.1043","article-title":"Frequent closed sequence mining without candidate maintenance","volume":"19","author":"Wang","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1089\/cmb.2019.0314","article-title":"Fast Approximation of Frequent k-mers and Applications to Metagenomics","volume":"27","author":"Pellegrina","year":"2019","journal-title":"J. Comput. Biol."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Riondato, M., and Vandin, F. (2018, January 19). MiSoSouP: Mining interesting subgroups with sampling and pseudodimension. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, UK.","DOI":"10.1145\/3219819.3219989"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Al Hasan, M., Chaoji, V., Salem, S., Besson, J., and Zaki, M.J. (2007, January 28\u201331). Origami: Mining representative orthogonal graph patterns. Proceedings of the Seventh IEEE International Conference on Data Mining (ICDM 2007), Omaha, NE, USA.","DOI":"10.1109\/ICDM.2007.45"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1186\/s40537-019-0207-2","article-title":"DENCAST: distributed density-based clustering for multi-target regression","volume":"6","author":"Corizzo","year":"2019","journal-title":"J. Big Data"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cheng, J., Fu, A.W.c., and Liu, J. (2010, January 6\u201311). K-isomorphism: privacy preserving network publication against structural attacks. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis, Indiana.","DOI":"10.1145\/1807167.1807218"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3208351","article-title":"ABRA: Approximating betweenness centrality in static and dynamic graphs with rademacher averages","volume":"12","author":"Riondato","year":"2018","journal-title":"ACM Trans. Knowl. Discov. D"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Mendes, L.F., Ding, B., and Han, J. (2008, January 15\u201319). Stream sequential pattern mining with precise error bounds. Proceedings of the Eighth IEEE International Conference on Data Mining, Pisa, Italy.","DOI":"10.1109\/ICDM.2008.154"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Pellegrina, L., Riondato, M., and Vandin, F. (2019, January 4\u20138). SPuManTE: Significant Pattern Mining with Unconditional Testing. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.","DOI":"10.1145\/3292500.3330978"},{"key":"ref_20","unstructured":"Zaki, M.J., Yu, J.X., Ravindran, B., and Pudi, V. (2010). Ranking Sequential Patterns with Respect to Significance. Advances in Knowledge Discovery and Data Mining, Springer."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Low-Kam, C., Ra\u00efssi, C., Kaytoue, M., and Pei, J. (2013, January 7\u201310). Mining statistically significant sequential patterns. Proceedings of the IEEE 13th International Conference on Data Mining, Dallas, TX, USA.","DOI":"10.1109\/ICDM.2013.124"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Tonon, A., and Vandin, F. (2019, January 8\u201311). Permutation Strategies for Mining Significant Sequential Patterns. Proceedings of the IEEE International Conference on Data Mining (ICDM), Beijing, China.","DOI":"10.1109\/ICDM.2019.00169"},{"key":"ref_23","unstructured":"Mitzenmacher, M., and Upfal, E. (2017). Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, Cambridge University Press."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"L\u00f6ffler, M., and Phillips, J.M. (2009). Shape fitting on point sets with probability distributions. Algorithms\u2013ESA 2009, Proceedings of the European Symposium on Algorithms, Copenhagen, Denmark, 7\u20139 September 2009, Springer.","DOI":"10.1007\/978-3-642-04128-0_29"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1006\/jcss.2000.1741","article-title":"Improved bounds on the sample complexity of learning","volume":"62","author":"Li","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9781107298019"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"732","DOI":"10.1007\/s10618-014-0362-1","article-title":"On measuring similarity for sequences of itemsets","volume":"29","author":"Egho","year":"2015","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_28","first-page":"36","article-title":"The SPMF open-source data mining library version 2","volume":"Volume 9853","author":"Berendt","year":"2016","journal-title":"Machine Learning and Knowledge Discovery in Databases"},{"key":"ref_29","unstructured":"Johnson, S.G. (2020, April 10). The NLopt Nonlinear-Optimization Package. Available online: https:\/\/nlopt.readthedocs.io\/en\/latest\/."},{"key":"ref_30","unstructured":"GitHub (2020, April 10). VCRadSPM: Mining Sequential Patterns with VC-Dimension and Rademacher Complexity. Available online: https:\/\/github.com\/VandinLab\/VCRadSPM."},{"key":"ref_31","unstructured":"(2020, April 10). SPMF Datasets. Available online: https:\/\/www.philippe-fournier-viger.com\/spmf\/index.php?link=datasets.php."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/5\/123\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:29:57Z","timestamp":1760174997000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/5\/123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,18]]},"references-count":31,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,5]]}},"alternative-id":["a13050123"],"URL":"https:\/\/doi.org\/10.3390\/a13050123","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,5,18]]}}}