{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T00:22:32Z","timestamp":1769905352364,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T00:00:00Z","timestamp":1518480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Youth Science Foundation","doi-asserted-by":"publisher","award":["1218325 and 1218318"],"award-info":[{"award-number":["1218325 and 1218318"]}],"id":[{"id":"10.13039\/100007515","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":[[2018,2,28]]},"abstract":"<jats:p>The problems of recurrent and anomalous pattern discovery in time series, e.g., motifs and discords, respectively, have received a lot of attention from researchers in the past decade. However, since the pattern search space is usually intractable, most existing detection algorithms require that the patterns have discriminative characteristics and have its length known in advance and provided as input, which is an unreasonable requirement for many real-world problems. In addition, patterns of similar structure, but of different lengths may co-exist in a time series. Addressing these issues, we have developed algorithms for variable-length time series pattern discovery that are based on symbolic discretization and grammar inference\u2014two techniques whose combination enables the structured reduction of the search space and discovery of the candidate patterns in linear time. In this work, we present GrammarViz 3.0\u2014a software package that provides implementations of proposed algorithms and graphical user interface for interactive variable-length time series pattern discovery. The current version of the software provides an alternative grammar inference algorithm that improves the time series motif discovery workflow, and introduces an experimental procedure for automated discretization parameter selection that builds upon the minimum cardinality maximum cover principle and aids the time series recurrent and anomalous pattern discovery.<\/jats:p>","DOI":"10.1145\/3051126","type":"journal-article","created":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T15:40:40Z","timestamp":1518536440000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["GrammarViz 3.0"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5517-7768","authenticated-orcid":false,"given":"Pavel","family":"Senin","sequence":"first","affiliation":[{"name":"Los Alamos National Laboratory, University Of Hawai\u2018i at M\u0101noa, Los Alamos, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jessica","family":"Lin","sequence":"additional","affiliation":[{"name":"George Mason University, Fairfax, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xing","family":"Wang","sequence":"additional","affiliation":[{"name":"George Mason University, Fairfax, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Oates","sequence":"additional","affiliation":[{"name":"University Of Maryland, Baltimore County, Baltimore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sunil","family":"Gandhi","sequence":"additional","affiliation":[{"name":"University Of Maryland, Baltimore County, Baltimore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnold P.","family":"Boedihardjo","sequence":"additional","affiliation":[{"name":"US Army Engineer Research and Development Center, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Crystal","family":"Chen","sequence":"additional","affiliation":[{"name":"US Army Engineer Research and Development Center, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susan","family":"Frankenstein","sequence":"additional","affiliation":[{"name":"US Army Engineer Research and Development Center, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170072"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655281"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 2008 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201908)","author":"Beaudoin Philippe","unstructured":"Philippe Beaudoin , Stelian Coros , Michiel van de Panne, and Pierre Poulin. 2008. Motion-motif graphs . In Proceedings of the 2008 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201908) . Eurographics Association, Aire-la-Ville, Switzerland, 117--126. Philippe Beaudoin, Stelian Coros, Michiel van de Panne, and Pierre Poulin. 2008. Motion-motif graphs. In Proceedings of the 2008 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201908). Eurographics Association, Aire-la-Ville, Switzerland, 117--126."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1089\/10665270252935430"},{"key":"e_1_2_1_5_1","volume-title":"Azevedo","author":"Castro Nuno","year":"2010","unstructured":"Nuno Castro and Paulo J . Azevedo . 2010 . Multiresolution motif discovery in time series. In Proceedings of the SDM. SIAM , 665--676. Nuno Castro and Paulo J. Azevedo. 2010. Multiresolution motif discovery in time series. In Proceedings of the SDM. SIAM, 665--676."},{"key":"e_1_2_1_6_1","volume-title":"Deepthi Cheboli, and Vipin Kumar.","author":"Chandola Varun","year":"2009","unstructured":"Varun Chandola . 2009. Detecting anomalies in a time series database Varun Chandola , Deepthi Cheboli, and Vipin Kumar. ( 2009 ). Varun Chandola. 2009. Detecting anomalies in a time series database Varun Chandola, Deepthi Cheboli, and Vipin Kumar. (2009)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956808"},{"key":"e_1_2_1_9_1","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin Richard","unstructured":"Richard Durbin , Sean R. Eddy , Anders Krogh , and Graeme Mitchison . 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids ( 1 st ed.). Cambridge University Press . Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids (1st ed.). Cambridge University Press.","edition":"1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/640075.640091"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1161\/01.CIR.101.23.e215"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP\u201995)","author":"Dina","unstructured":"Dina Q. Goldin and Paris C. Kanellakis. 1995. On similarity queries for time-series data: Constraint specification and implementation . In Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP\u201995) . Springer-Verlag, London, UK, 137--153. http:\/\/dl.acm.org\/citation.cfm?id&equals;647484.726176. Dina Q. Goldin and Paris C. Kanellakis. 1995. On similarity queries for time-series data: Constraint specification and implementation. In Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP\u201995). Springer-Verlag, London, UK, 137--153. http:\/\/dl.acm.org\/citation.cfm?id&equals;647484.726176."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940329"},{"key":"e_1_2_1_14_1","volume-title":"The Minimum Description Length Principle","author":"Gr\u00fcnwald Peter D.","unstructured":"Peter D. Gr\u00fcnwald . 2007. The Minimum Description Length Principle . MIT press . Peter D. Gr\u00fcnwald. 2007. The Minimum Description Length Principle. MIT press."},{"key":"e_1_2_1_15_1","first-page":"9","article-title":"Outlier detection for temporal data: A survey. Knowledge and Data Engineering","volume":"26","author":"Gupta M.","year":"2014","unstructured":"M. Gupta , Jing Gao , C. C. Aggarwal , and Jiawei Han . 2014 . Outlier detection for temporal data: A survey. Knowledge and Data Engineering , IEEE Transactions on 26 , 9 (Sep. 2014), 2250--2267. M. Gupta, Jing Gao, C. C. Aggarwal, and Jiawei Han. 2014. Outlier detection for temporal data: A survey. Knowledge and Data Engineering, IEEE Transactions on 26, 9 (Sep. 2014), 2250--2267.","journal-title":"IEEE Transactions on"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.015"},{"key":"e_1_2_1_17_1","volume-title":"IEEE Engineering in Medicine and Biology Society. Annual Conference 1","author":"He Dan","year":"2006","unstructured":"Dan He . 2006 . Using suffix tree to discover complex repetitive patterns in DNA sequences.Conference Proceedings : \u2026 Annual International Conference of the IEEE Engineering in Medicine and Biology Society . IEEE Engineering in Medicine and Biology Society. Annual Conference 1 (2006), 3474--3477. Dan He. 2006. Using suffix tree to discover complex repetitive patterns in DNA sequences.Conference Proceedings : \u2026 Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual Conference 1 (2006), 3474--3477."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3182688.3183134"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2010.2081372"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the SDM.","author":"Kawahara Yoshinobu","unstructured":"Yoshinobu Kawahara and Masashi Sugiyama . 2009. Change-point detection in time-series data by direct density-ratio estimation . In Proceedings of the SDM. Vol. 9 . SIAM , 389--400. Yoshinobu Kawahara and Masashi Sugiyama. 2009. Change-point detection in time-series data by direct density-ratio estimation. In Proceedings of the SDM. Vol. 9. SIAM, 389--400."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.79"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014077"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11192"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings Data Compression Conference (DCC\u201999)","author":"Larsson N. J.","unstructured":"N. J. Larsson and A. Moffat . 1999. Offline dictionary-based compression . In Proceedings Data Compression Conference (DCC\u201999) . 296--305. N. J. Larsson and A. Moffat. 1999. Offline dictionary-based compression. In Proceedings Data Compression Conference (DCC\u201999). 296--305."},{"key":"e_1_2_1_25_1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"Li Ming","unstructured":"Ming Li and Paul Vit\u00e1nyi . 2013. An Introduction to Kolmogorov Complexity and Its Applications . Springer Science 8 Business Media. Ming Li and Paul Vit\u00e1nyi. 2013. An Introduction to Kolmogorov Complexity and Its Applications. Springer Science 8 Business Media."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.77"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/882082.882086"},{"key":"e_1_2_1_28_1","unstructured":"Jessica Lin Eamonn Keogh Stefano Lonardi and Pranav Patel. 2002. Finding motifs in time series. (2002) 53--68.  Jessica Lin Eamonn Keogh Stefano Lonardi and Pranav Patel. 2002. Finding motifs in time series. (2002) 53--68."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-007-0064-z"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the EUROGRAPHICS.","volume":"8","author":"Meng Jingjing","year":"2008","unstructured":"Jingjing Meng , Junsong Yuan , Mat Hans , and Ying Wu . 2008 . Mining motifs from human motion . In Proceedings of the EUROGRAPHICS. Vol. 8 . Jingjing Meng, Junsong Yuan, Mat Hans, and Ying Wu. 2008. Mining motifs from human motion. In Proceedings of the EUROGRAPHICS. Vol. 8."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence.","author":"Minnen David","year":"2007","unstructured":"David Minnen , Charles L. Isbell , Irfan Essa , and Thad Starner . 2007 . Discovering multivariate motifs using subsequence density estimation . In Proceedings of the AAAI Conference on Artificial Intelligence. David Minnen, Charles L. Isbell, Irfan Essa, and Thad Starner. 2007. Discovering multivariate motifs using subsequence density estimation. In Proceedings of the AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_33_1","volume-title":"The Learning Workshop (SNOWBIRD).","author":"Minnen David","year":"2006","unstructured":"David Minnen , Thad Starner , Irfan Essa , and Charles Isbell . 2006 . Activity discovery: Sparse motifs from multivariate time series . In The Learning Workshop (SNOWBIRD). David Minnen, Thad Starner, Irfan Essa, and Charles Isbell. 2006. Activity discovery: Sparse motifs from multivariate time series. In The Learning Workshop (SNOWBIRD)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05458-2_3"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0793-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.41"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622776.1622780"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Data Compression Conference (DCC\u201997)","author":"Craig","unstructured":"Craig G. Nevill-Manning and Ian H. Witten. 1997. Linear-time, incremental hierarchy inference for compression . In Proceedings of the Data Compression Conference (DCC\u201997) . IEEE, 3--11. Craig G. Nevill-Manning and Ian H. Witten. 1997. Linear-time, incremental hierarchy inference for compression. In Proceedings of the Data Compression Conference (DCC\u201997). IEEE, 3--11."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 8th International Conference on Electrical Engineering\/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON\u201911)","author":"Nunthanid P.","unstructured":"P. Nunthanid , V. Niennattrakul , and C. A. Ratanamahatana . 2011. Discovery of variable length time series motif . In Proceedings of the 8th International Conference on Electrical Engineering\/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON\u201911) . 472--475. P. Nunthanid, V. Niennattrakul, and C. A. Ratanamahatana. 2011. Discovery of variable length time series motif. In Proceedings of the 8th International Conference on Electrical Engineering\/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON\u201911). 472--475."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/844380.844732"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/844380.844710"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSVT.2008.2005599"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Conference on Extending Database Technology.","author":"Senin Pavel","year":"2015","unstructured":"Pavel Senin , Jessica Lin , Xing Wang , Tim Oates , Sunil Gandhi , Arnold P. Boedihardjo , Crystal Chen , and Susan Frankenstein . 2015 . Time series anomaly discovery with grammar-based compression . In Proceedings of the International Conference on Extending Database Technology. Pavel Senin, Jessica Lin, Xing Wang, Tim Oates, Sunil Gandhi, Arnold P. Boedihardjo, Crystal Chen, and Susan Frankenstein. 2015. Time series anomaly discovery with grammar-based compression. In Proceedings of the International Conference on Extending Database Technology."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44845-8_37"},{"key":"e_1_2_1_45_1","first-page":"4","article-title":"Methods for discovering novel motifs in nucleic acid sequences. Computer Applications in the Biosciences","volume":"5","author":"Staden R.","year":"1989","unstructured":"R. Staden . 1989 . Methods for discovering novel motifs in nucleic acid sequences. Computer Applications in the Biosciences : CABIOS 5 , 4 (Oct. 1989), 293--298. R. Staden. 1989. Methods for discovering novel motifs in nucleic acid sequences. Computer Applications in the Biosciences : CABIOS 5, 4 (Oct. 1989), 293--298.","journal-title":"CABIOS"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-005-5829-2"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 18th Annual Conference of the Japanese Society for Artificial Intelligence.","author":"Tanaka Yoshiki","year":"2004","unstructured":"Yoshiki Tanaka and Kuniaki Uehara . 2004 . Motif discovery algorithm from motion data . In Proceedings of the 18th Annual Conference of the Japanese Society for Artificial Intelligence. Yoshiki Tanaka and Kuniaki Uehara. 2004. Motif discovery algorithm from motion data. In Proceedings of the 18th Annual Conference of the Japanese Society for Artificial Intelligence."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2008.03.022"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339606"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07821-2_8"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of 1999 IEEE Symposium on Information Visualization (Info Vis\u201999)","author":"Jarke","unstructured":"Jarke J. Van Wijk and Edward R. Van Selow. 1999. Cluster and calendar based visualization of time series data . In Proceedings of 1999 IEEE Symposium on Information Visualization (Info Vis\u201999) . IEEE, 4--9. Jarke J. Van Wijk and Edward R. Van Selow. 1999. Cluster and calendar based visualization of time series data. In Proceedings of 1999 IEEE Symposium on Information Visualization (Info Vis\u201999). IEEE, 4--9."},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"M. S. Vitevitch P. A. Luce J. Charles-Luce and D. Kemmerer. 1997. Phonotactics and syllable stress: Implications for the processing of spoken nonsense words. Language and Speech 40 (Pt. 1) (1997) 47--62.  M. S. Vitevitch P. A. Luce J. Charles-Luce and D. Kemmerer. 1997. Phonotactics and syllable stress: Implications for the processing of spoken nonsense words. Language and Speech 40 (Pt. 1) (1997) 47--62.","DOI":"10.1177\/002383099704000103"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.138"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1473147.1473152"},{"key":"e_1_2_1_55_1","volume-title":"Encyclopedia of Algorithms, Ming-Yang Kao (Ed.)","author":"Young Neal E.","unstructured":"Neal E. Young . 2008. Greedy set-cover algorithms . In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.) . Springer , 379--381. Neal E. Young. 2008. Greedy set-cover algorithms. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer, 379--381."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051126","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3051126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:39Z","timestamp":1750222479000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051126"}},"subtitle":["Interactive Discovery of Variable-Length Time Series Patterns"],"short-title":[],"issued":{"date-parts":[[2018,2,13]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3051126"],"URL":"https:\/\/doi.org\/10.1145\/3051126","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,13]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}