{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:44Z","timestamp":1750220924473,"version":"3.41.0"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T00:00:00Z","timestamp":1553644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>Negative sequential patterns (NSPs) produced by negative sequence analysis (NSA) capture more informative and actionable knowledge than classic positive sequential patterns (PSPs) due to involving both occurring and nonoccurring items, which appear in many applications. However, the research on NSA is still at an early stage, and NSP mining involves very high computational complexity and a very large search space, there is no widely accepted problem statement on NSP mining, and different settings on constraints and negative containment have been proposed in existing work. Among existing NSP mining algorithms, there are no general and systemic evaluation criteria available to assess them comprehensively. This article conducts a comprehensive technical review of existing NSA research. We explore and formalize a generic problem statement of NSA; investigate, compare, and consolidate the definitions of constraints and negative containment; and compare the working mechanisms and efficiency of existing NSP mining algorithms. The review is concluded by discussing new research opportunities in NSA.<\/jats:p>","DOI":"10.1145\/3311952","type":"journal-article","created":{"date-parts":[[2019,3,28]],"date-time":"2019-03-28T12:23:24Z","timestamp":1553775804000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Negative Sequence Analysis"],"prefix":"10.1145","volume":"52","author":[{"given":"Wei","family":"Wang","sequence":"first","affiliation":[{"name":"University of Technology Sydney, New SouthWales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1562-9429","authenticated-orcid":false,"given":"Longbing","family":"CAO","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, New SouthWales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/IS.2010.5548370"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.28"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775109"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.03.025"},{"key":"e_1_2_2_5_1","unstructured":"Longbing Cao. 2012. Combined mining: Analyzing object and pattern relations for discovering actionable complex patterns. Sponsored by Australian Research Council Discovery Grants (DP1096218 and DP130102691) and an ARC Linkage Grant (LP100200774).  Longbing Cao. 2012. Combined mining: Analyzing object and pattern relations for discovering actionable complex patterns. Sponsored by Australian Research Council Discovery Grants (DP1096218 and DP130102691) and an ARC Linkage Grant (LP100200774)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxt084"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2014.08.007"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.03.001"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.129"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835818"},{"volume-title":"Domain Driven Data Mining","author":"Cao Longbing","key":"e_1_2_2_11_1","unstructured":"Longbing Cao , Philip Yu , Yanchang Zhao , and Chengqi Zhang . 2010. Domain Driven Data Mining . Springer . Longbing Cao, Philip Yu, Yanchang Zhao, and Chengqi Zhang. 2010. Domain Driven Data Mining. Springer."},{"key":"e_1_2_2_12_1","volume-title":"Yu","author":"Cao Longbing","year":"2012","unstructured":"Longbing Cao and Philip S . Yu . 2012 . Behavior Computing\u2014Modeling, Analysis, Mining and Decision. Springer . Longbing Cao and Philip S. Yu. 2012. Behavior Computing\u2014Modeling, Analysis, Mining and Decision. Springer."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2015.105"},{"volume-title":"Data Mining for Business Applications","author":"Cao Longbing","key":"e_1_2_2_14_1","unstructured":"Longbing Cao , Philip S. Yu , Chengqi Zhang , and Huaifeng Zhang . 2008. Data Mining for Business Applications . Springer . Longbing Cao, Philip S. Yu, Chengqi Zhang, and Huaifeng Zhang. 2008. Data Mining for Business Applications. Springer."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190635"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.143"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014114"},{"volume-title":"Proceedings of the 20th International Conference on Data Engineering. IEEE","author":"Chiu Ding-Ying","key":"e_1_2_2_18_1","unstructured":"Ding-Ying Chiu , Yi-Hung Wu , and Arbee L. P. Chen . 2004. An efficient algorithm for mining frequent sequences by a new strategy without support counting . In Proceedings of the 20th International Conference on Data Engineering. IEEE , Los Alamitos, CA, 375--386. Ding-Ying Chiu, Yi-Hung Wu, and Arbee L. P. Chen. 2004. An efficient algorithm for mining frequent sequences by a new strategy without support counting. In Proceedings of the 20th International Conference on Data Engineering. IEEE, Los Alamitos, CA, 375--386."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWECA.2014.6845638"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11811305_10"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06608-0_4"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-015-0884-x"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases (VLDB\u201999)","author":"Garofalakis Minos N.","year":"1999","unstructured":"Minos N. Garofalakis , Rajeev Rastogi , and Kyuseok Shim . 1999 . SPIRIT: Sequential pattern mining with regular expression constraints . In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB\u201999) . 223--234. Minos N. Garofalakis, Rajeev Rastogi, and Kyuseok Shim. 1999. SPIRIT: Sequential pattern mining with regular expression constraints. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB\u201999). 223--234."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37453-1_5"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.2174\/1874444301507010934"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001417500021"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0059-1"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/APSCC.2008.183"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICICEE.2012.32"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Xiaoqi Jiang Qian Gao Tiantian Xu and Xiangjun Dong. 2018. Campus data analysis based on positive and negative sequential patterns. International Journal of Pattern Recognition and Artificial Intelligence.  Xiaoqi Jiang Qian Gao Tiantian Xu and Xiangjun Dong. 2018. Campus data analysis based on positive and negative sequential patterns. International Journal of Pattern Recognition and Artificial Intelligence.","DOI":"10.1142\/S021800141959016X"},{"key":"e_1_2_2_31_1","first-page":"15","article-title":"Frequent negative sequential patterns: A survey","volume":"5","author":"Kamepalli S.","year":"2014","unstructured":"S. Kamepalli and R. Kurra . 2014 . Frequent negative sequential patterns: A survey . International Journal of Computer Engineering and Technology 5 , 3 (2014), 15 -- 121 . S. Kamepalli and R. Kurra. 2014. Frequent negative sequential patterns: A survey. International Journal of Computer Engineering and Technology 5, 3 (2014), 15--121.","journal-title":"International Journal of Computer Engineering and Technology"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5120\/12322-8539"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1032-6"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-014-0630-1"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835900"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the 6th WSEAS International Conference on Applied Computer Science. 654--658","author":"Lin Nancy P.","year":"2007","unstructured":"Nancy P. Lin , Hung-Jen Chen , and Wei-Hua Hao . 2007 . Mining negative sequential patterns . In Proceedings of the 6th WSEAS International Conference on Applied Computer Science. 654--658 . Nancy P. Lin, Hung-Jen Chen, and Wei-Hua Hao. 2007. Mining negative sequential patterns. In Proceedings of the 6th WSEAS International Conference on Applied Computer Science. 654--658."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1457907.1457913"},{"key":"e_1_2_2_38_1","first-page":"167","article-title":"An algorithm for mining strong negative fuzzy sequential patterns","volume":"1","author":"Lin Nancy P.","year":"2007","unstructured":"Nancy P. Lin , Wei-Hua Hao , Hung-Jen Chen , Chung- I Chang , and Hao-En Chueh . 2007 . An algorithm for mining strong negative fuzzy sequential patterns . International Journal of Computers 1 , 3 (2007), 167 -- 172 . Nancy P. Lin, Wei-Hua Hao, Hung-Jen Chen, Chung-I Chang, and Hao-En Chueh. 2007. An algorithm for mining strong negative fuzzy sequential patterns. International Journal of Computers 1, 3 (2007), 167--172.","journal-title":"International Journal of Computers"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD\u201915)","author":"Liu Chuanlu","year":"2015","unstructured":"Chuanlu Liu , Xiangjun Dong , Caoyuan Li , and Yan Li . 2015 . SAPNSP: Select actionable positive and negative sequential patterns based on a contribution metric . In Proceedings of the 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD\u201915) . IEEE, Los Alamitos, CA, 811--815. Chuanlu Liu, Xiangjun Dong, Caoyuan Li, and Yan Li. 2015. SAPNSP: Select actionable positive and negative sequential patterns based on a contribution metric. In Proceedings of the 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD\u201915). IEEE, Los Alamitos, CA, 811--815."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431218"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/GCIS.2009.69"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/GCIS.2010.213"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSKD.2008.245"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLC.2007.4370257"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/568574.568580"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.77"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584799"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-006-0006-z"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2029759.2029802"},{"volume-title":"Proceedings of the 2011 IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing (PacRim\u201911)","author":"Soliman Amany F.","key":"e_1_2_2_50_1","unstructured":"Amany F. Soliman , Gamal A. Ebrahim , and Hoda K. Mohammed . 2011. SPEDS: A framework for mining sequential patterns in evolving data streams . In Proceedings of the 2011 IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing (PacRim\u201911) . IEEE, Los Alamitos, CA, 464--469. Amany F. Soliman, Gamal A. Ebrahim, and Hoda K. Mohammed. 2011. SPEDS: A framework for mining sequential patterns in evolving data streams. In Proceedings of the 2011 IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing (PacRim\u201911). IEEE, Los Alamitos, CA, 464--469."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339683"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/645337.650382"},{"volume-title":"Information Engineering and Applications","author":"Tao Zaiping","key":"e_1_2_2_53_1","unstructured":"Zaiping Tao . 2012. An incremental update algorithm for sequential patterns mining . In Information Engineering and Applications . Springer , 134--140. Zaiping Tao. 2012. An incremental update algorithm for sequential patterns mining. In Information Engineering and Applications. Springer, 134--140."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2993952.2994023"},{"volume-title":"Behavior Computing","author":"Wang Can","key":"e_1_2_2_55_1","unstructured":"Can Wang and Longbing Cao . 2012. Modeling and analysis of social activity process . In Behavior Computing . Springer , 21--35. Can Wang and Longbing Cao. 2012. Modeling and analysis of social activity process. In Behavior Computing. Springer, 21--35."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2015.2399862"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544840"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339546"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1010614.1010616"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001417500355"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001417500033"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783823.1783946"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339636"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.148"},{"volume-title":"Proceedings of the 13th International Conference on GeoComputation Geospatial Information Sciences.","author":"Yusof N.","key":"e_1_2_2_65_1","unstructured":"N. Yusof , R. Zurita-Milla , and M. J. Kraak . 2015. Mining sequential pattern of multi-dimensional wind profiles . In Proceedings of the 13th International Conference on GeoComputation Geospatial Information Sciences. N. Yusof, R. Zurita-Milla, and M. J. Kraak. 2015. Mining sequential pattern of multi-dimensional wind profiles. In Proceedings of the 13th International Conference on GeoComputation Geospatial Information Sciences."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354849"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007652502315"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/WIIAT.2008.60"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01307-2_65"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1288552.1288555"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04174-7_42"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-015-0350-4"},{"key":"e_1_2_2_74_1","volume-title":"Proceedings of the 8th Australasian Data Mining Conference\u2014Volume 101","author":"Zheng Zhigang","year":"2009","unstructured":"Zhigang Zheng , Yanchang Zhao , Ziye Zuo , and Longbing Cao . 2009 . Negative-GSP: An efficient method for mining negative sequential patterns . In Proceedings of the 8th Australasian Data Mining Conference\u2014Volume 101 . 63--67. Zhigang Zheng, Yanchang Zhao, Ziye Zuo, and Longbing Cao. 2009. Negative-GSP: An efficient method for mining negative sequential patterns. In Proceedings of the 8th Australasian Data Mining Conference\u2014Volume 101. 63--67."},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13657-3_30"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3311952","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3311952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:12Z","timestamp":1750204392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3311952"}},"subtitle":["A Review"],"short-title":[],"issued":{"date-parts":[[2019,3,27]]},"references-count":74,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3311952"],"URL":"https:\/\/doi.org\/10.1145\/3311952","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2019,3,27]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}