{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:27:04Z","timestamp":1772206024978,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,3,1]],"date-time":"2012-03-01T00:00:00Z","timestamp":1330560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["60873171"],"award-info":[{"award-number":["60873171"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004602","name":"Program for New Century Excellent Talents in University","doi-asserted-by":"publisher","award":["NCET-07-0491"],"award-info":[{"award-number":["NCET-07-0491"]}],"id":[{"id":"10.13039\/501100004602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2011CB302206"],"award-info":[{"award-number":["2011CB302206"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p>Mining frequent subsequence patterns is a typical data-mining problem and various efficient sequential pattern mining algorithms have been proposed. In many application domains (e.g., biology), the frequent subsequences confined by the predefined gap requirements are more meaningful than the general sequential patterns. In this article, we propose two algorithms, Gap-BIDE for mining closed gap-constrained subsequences from a set of input sequences, and Gap-Connect for mining repetitive gap-constrained subsequences from a single input sequence. Inspired by some state-of-the-art closed or constrained sequential pattern mining algorithms, the Gap-BIDE algorithm adopts an efficient approach to finding the complete set of closed sequential patterns with gap constraints, while the Gap-Connect algorithm efficiently mines an approximate set of long patterns by connecting short patterns. We also present several methods for feature selection from the set of gap-constrained patterns for the purpose of classification and clustering. Our extensive performance study shows that our approaches are very efficient in mining frequent subsequences with gap constraints, and the gap-constrained pattern based classification\/clustering approaches can achieve high-quality results.<\/jats:p>","DOI":"10.1145\/2133360.2133362","type":"journal-article","created":{"date-parts":[[2012,3,27]],"date-time":"2012-03-27T15:17:31Z","timestamp":1332861451000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["Efficient Mining of Gap-Constrained Subsequences and Its Various Applications"],"prefix":"10.1145","volume":"6","author":[{"given":"Chun","family":"Li","sequence":"first","affiliation":[{"name":"Tsinghua University"}]},{"given":"Qingyan","family":"Yang","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]},{"given":"Jianyong","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]}],"member":"320","published-online":{"date-parts":[[2012,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281201"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 11th International Conference on Data Engineering (ICDE). IEEE, 3--14","author":"Agrawal R."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775109"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.34"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Chandonia J. M. Hon G. Walker N. S. Lo Conte L. Koehl P. Levitt M. and Brenner S. E. 2004. The ASTRAL compendium in 2004. Nucl. Acids Res. 32 (Database issue). Chandonia J. M. Hon G. Walker N. S. Lo Conte L. Koehl P. Levitt M. and Brenner S. E. 2004. The ASTRAL compendium in 2004. Nucl. Acids Res. 32 (Database issue).","DOI":"10.1093\/nar\/gkh034"},{"key":"e_1_2_1_6_1","unstructured":"Chang C.-C. and Lin C.-J. 2001. LIBSVM: A library for support vector machines. http:\/\/www.csie.ntu.edu.tw\/ cjlin\/libsvm. Chang C.-C. and Lin C.-J. 2001. LIBSVM: A library for support vector machines . http:\/\/www.csie.ntu.edu.tw\/ cjlin\/libsvm."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242753"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497425"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 6th Pacific-Asia Cinference on Knowledge Discovery and Data Mining (PAKDD). 417--431","author":"Deshpande M."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976698300017197"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2007.02.009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367651"},{"key":"e_1_2_1_14_1","volume-title":"Spirit: Sequential pattern mining with regular expression constraints. In Proceedings of 25th International Conference on Very Large Data Bases (VLDB)","author":"Garofalakis M. N.","year":"1999"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 15th International Conference on Data Engineering, IEEE Computer Society, 106--115","author":"Han J."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347167"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346830"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.96"},{"key":"e_1_2_1_19_1","volume-title":"Pac Symp Biocomput, 564--575","author":"Leslie C."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST). USENIX Association","author":"Li Z."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2006.28"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1181775.1181808"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 14th Conference on Neural Information Processing Systems (NIPS). 563--569","author":"Lodhi H."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009748302351"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2nd European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD). Springer-Verlag, 176--184","author":"Masseglia F."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-006-0006-z"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings 17th International Conference on Data Engineering. 215--226","author":"Pei J."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.57"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/14.1.55"},{"key":"e_1_2_1_30_1","volume-title":"IJCAI-01 Workshop on Empirical Methods in AI.","author":"Rish I.","year":"2001"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401961"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/844380.844726"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956800"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 5th International Conference on Extending Database Technology (EDBT). P. M. G. Apers, M. Bouzeghoub, and G. Gardarin Eds., Springer-Verlag","volume":"1057","author":"Srikant R."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2005 SIAM International Conference on Data Mining (SDM).","author":"Wang J."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1043"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-008-0100-7"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). Tutorial.","author":"Xie T."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 2003 SIAM International Conference on Data Mining (SDM). 166--177","author":"Yan X."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564738"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007652502315"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1267066.1267068"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI). 2934--2941","author":"Zhu X."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.75"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference on Data Engineering. 706--715","author":"Zhu F."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133360.2133362","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133360.2133362","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:05Z","timestamp":1750241165000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133360.2133362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1145\/2133360.2133362"],"URL":"https:\/\/doi.org\/10.1145\/2133360.2133362","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}