{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T14:09:45Z","timestamp":1774620585017,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,4]]},"abstract":"<jats:p>Modern<jats:italic>Internet of Things<\/jats:italic>(<jats:italic>IoT<\/jats:italic>) applications generate massive amounts of time-stamped data, much of it in the form of discrete, symbolic sequences. In this work, we present a new system called TOP that de&lt;u&gt;T&lt;\/u&gt;ects &lt;u&gt;O&lt;\/u&gt;utlier &lt;u&gt;P&lt;\/u&gt;atterns from these sequences. To solve the fundamental limitation of existing pattern mining semantics that miss outlier patterns hidden inside of larger frequent patterns, TOP offers new pattern semantics based on<jats:italic>contextual patterns<\/jats:italic>that distinguish the<jats:italic>independent occurrence<\/jats:italic>of a pattern from its occurrence as part of its super-pattern. We present efficient algorithms for the mining of this new class of contextual patterns. In particular, in contrast to the bottom-up strategy for state-of-the-art pattern mining techniques, our top-down<jats:italic>Reduce<\/jats:italic>strategy piggy backs pattern detection with the detection of the context in which a pattern occurs. Our approach achieves linear time complexity in the length of the input sequence. Effective optimization techniques such as context-driven search space pruning and inverted index-based outlier pattern detection are also proposed to further speed up contextual pattern mining. Our experimental evaluation demonstrates the effectiveness of TOP at capturing meaningful outlier patterns in several real-world IoT use cases. We also demonstrate the efficiency of TOP, showing it to be up to 2 orders of magnitude faster than adapting state-of-the-art mining to produce this new class of contextual outlier patterns, allowing us to scale outlier pattern mining to large sequence datasets.<\/jats:p>","DOI":"10.14778\/3324301.3324308","type":"journal-article","created":{"date-parts":[[2019,6,24]],"date-time":"2019-06-24T13:43:16Z","timestamp":1561383796000},"page":"920-932","source":"Crossref","is-referenced-by-count":10,"title":["Efficient discovery of sequence outlier patterns"],"prefix":"10.14778","volume":"12","author":[{"given":"Lei","family":"Cao","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yizhou","family":"Yan","sequence":"additional","affiliation":[{"name":"Worcester Polytechnic Institute Worcester"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Madden","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elke A.","family":"Rundensteiner","sequence":"additional","affiliation":[{"name":"Worcester Polytechnic Institute Worcester"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathan","family":"Gopalsamy","sequence":"additional","affiliation":[{"name":"Signify Research, Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-07821-2","volume-title":"Frequent Pattern Mining","author":"Aggarwal C. C.","year":"2014","unstructured":"C. C. Aggarwal and J. Han , editors . Frequent Pattern Mining . Springer , 2014 . C. C. Aggarwal and J. Han, editors. Frequent Pattern Mining. Springer, 2014."},{"key":"e_1_2_1_2_1","first-page":"490","volume-title":"VLDB","author":"Agrawal R.","year":"1995","unstructured":"R. Agrawal , K.-I. Lin , H. S. Sawhney , and K. Shim . Fast similarity search in the presence of noise, scaling, and translation in time-series databases . In VLDB , pages 490 -- 501 , San Francisco, CA, USA , 1995 . R. Agrawal, K.-I. Lin, H. S. Sawhney, and K. Shim. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In VLDB, pages 490--501, San Francisco, CA, USA, 1995."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655281"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775109"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2757217"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2008.2007248"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.235"},{"key":"e_1_2_1_8_1","volume-title":"The UCR time series archive. CoRR, abs\/1810.07758","author":"Dau H. A.","year":"2018","unstructured":"H. A. Dau , A. J. Bagnall , K. Kamgar , C. M. Yeh , Y. Zhu , S. Gharghabi , C. A. Ratanamahatana , and E. J. Keogh . The UCR time series archive. CoRR, abs\/1810.07758 , 2018 . H. A. Dau, A. J. Bagnall, K. Kamgar, C. M. Yeh, Y. Zhu, S. Gharghabi, C. A. Ratanamahatana, and E. J. Keogh. The UCR time series archive. CoRR, abs\/1810.07758, 2018."},{"key":"e_1_2_1_9_1","first-page":"40","volume-title":"PAKDD","author":"Fournier-Viger P.","year":"2014","unstructured":"P. Fournier-Viger , A. Gomariz , M. Campos , and R. Thomas . Fast vertical mining of seq. patterns using co-occurrence information . In PAKDD , pages 40 -- 52 , 2014 . P. Fournier-Viger, A. Gomariz, M. Campos, and R. Thomas. Fast vertical mining of seq. patterns using co-occurrence information. In PAKDD, pages 40--52, 2014."},{"issue":"1","key":"e_1_2_1_10_1","first-page":"54","article-title":"A survey of sequential pattern mining","volume":"1","author":"Fournier-Viger P.","year":"2017","unstructured":"P. Fournier-Viger , J. C.-W. Lin , R. U. Kiran , and Y. S. Koh . A survey of sequential pattern mining . Data Science and Pattern Recognition , 1 ( 1 ): 54 -- 77 , 2017 . P. Fournier-Viger, J. C.-W. Lin, R. U. Kiran, and Y. S. Koh. A survey of sequential pattern mining. Data Science and Pattern Recognition, 1(1):54--77, 2017.","journal-title":"Data Science and Pattern Recognition"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06483-3_8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-53914-5_15"},{"key":"e_1_2_1_13_1","first-page":"50","volume-title":"PAKDD","author":"Gomariz A.","year":"2013","unstructured":"A. Gomariz , M. Campos , R. Marin , and B. Goethals . Clasp: An efficient algorithm for mining frequent closed sequences . In PAKDD , pages 50 -- 61 . Springer , 2013 . A. Gomariz, M. Campos, R. Marin, and B. Goethals. Clasp: An efficient algorithm for mining frequent closed sequences. In PAKDD, pages 50--61. Springer, 2013."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.33"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347167"},{"key":"e_1_2_1_16_1","first-page":"215","volume-title":"ICDE","author":"Han J.","year":"2001","unstructured":"J. Han , J. Pei , B. Mortazavi-Asl , H. Pinto , Q. Chen , U. Dayal , and M. Hsu . Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth . In ICDE , pages 215 -- 224 , 2001 . J. Han, J. Pei, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. Hsu. Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In ICDE, pages 215--224, 2001."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-980109"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ANTHOLOGY.2013.6784864"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.79"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225652.3225900"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775128"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.05.021"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281238"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CBMS.2005.34"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2008.11.033"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.37"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009748302351"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2029759.2029802"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645337.650382"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339606"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2021017.2021021"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1043"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.1999.766910"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487654"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972733.15"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.235"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/599609.599626"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3324301.3324308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T18:25:13Z","timestamp":1694975113000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3324301.3324308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4]]},"references-count":37,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["10.14778\/3324301.3324308"],"URL":"https:\/\/doi.org\/10.14778\/3324301.3324308","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,4]]}}}