{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T23:37:52Z","timestamp":1722987472500},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>\n            Subsequence matching is an important and fundamental problem on time series data. This paper studies the inherent time complexity of the subsequence matching problem and designs a more efficient algorithm for solving the problem. Firstly, it is proved that the subsequence matching problem is incomputable in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1-\u03b4<\/jats:sup>\n            ) even allowing polynomial time preprocessing if the hypothesis SETH is true, where\n            <jats:italic>n<\/jats:italic>\n            is the size of the input time series and 0 \u2264 \u03b4 &lt; 1, i.e., the inherent complexity of the subsequence matching problem is\n            <jats:italic>\u03c9<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1-\u03b4<\/jats:sup>\n            ). Secondly, an efficient algorithm for subsequence matching problem is proposed. In order to improve the efficiency of the algorithm, we design a new summarization method as well as a novel index for series data. The proposed algorithm supports both Euclidean Distance and DTW distance with or without\n            <jats:italic>z<\/jats:italic>\n            -normalization. Experimental results show that the proposed algorithm is up to about 3 ~ 10 times faster than the state of art algorithm on the constrained\n            <jats:italic>z<\/jats:italic>\n            -normalized Euclidean Distance and DTW distance, and is up to 7 ~ 12 times faster on Euclidean Distance.\n          <\/jats:p>","DOI":"10.14778\/3523210.3523222","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:21Z","timestamp":1655936601000},"page":"1453-1465","source":"Crossref","is-referenced-by-count":2,"title":["The inherent time complexity and an efficient algorithm for subsequence matching problem"],"prefix":"10.14778","volume":"15","author":[{"given":"Zemin","family":"Chao","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Gao","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinan","family":"An","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology Chinese, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00052"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00023"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00052"},{"key":"e_1_2_1_4_1","volume-title":"On the hardness of approximate and exact (bichromatic) maximum inner product. arXiv preprint arXiv:1802.02325","author":"Chen Lijie","year":"2018","unstructured":"Lijie Chen . 2018. On the hardness of approximate and exact (bichromatic) maximum inner product. arXiv preprint arXiv:1802.02325 ( 2018 ). Lijie Chen. 2018. On the hardness of approximate and exact (bichromatic) maximum inner product. arXiv preprint arXiv:1802.02325 (2018)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316758"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_2_1_7_1","volume-title":"The lernaean hydra of data series similarity search: An experimental evaluation of the state of the art. arXiv preprint arXiv:2006.11454","author":"Echihabi Karima","year":"2020","unstructured":"Karima Echihabi , Kostas Zoumpatianos , Themis Palpanas , and Houda Benbrahim . 2020. The lernaean hydra of data series similarity search: An experimental evaluation of the state of the art. arXiv preprint arXiv:2006.11454 ( 2020 ). Karima Echihabi, Kostas Zoumpatianos, Themis Palpanas, and Houda Benbrahim. 2020. The lernaean hydra of data series similarity search: An experimental evaluation of the state of the art. arXiv preprint arXiv:2006.11454 (2020)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325902"},{"key":"e_1_2_1_10_1","unstructured":"Yoonho Hwang and Hee-Kap Ahn. 2011. Convergent bounds on the euclidean distance. In Advances in neural information processing systems. 388--396.  Yoonho Hwang and Hee-Kap Ahn. 2011. Convergent bounds on the euclidean distance. In Advances in neural information processing systems. 388--396."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1999.757470"},{"key":"e_1_2_1_13_1","volume-title":"Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems 3, 3","author":"Keogh Eamonn","year":"2001","unstructured":"Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , and Sharad Mehrotra . 2001. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems 3, 3 ( 2001 ), 263--286. Eamonn Keogh, Kaushik Chakrabarti, Michael Pazzani, and Sharad Mehrotra. 2001. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems 3, 3 (2001), 263--286."},{"key":"e_1_2_1_14_1","volume-title":"Exact indexing of dynamic time warping. Knowledge and information systems 7, 3","author":"Keogh Eamonn","year":"2005","unstructured":"Eamonn Keogh and Chotirat Ann Ratanamahatana . 2005. Exact indexing of dynamic time warping. Knowledge and information systems 7, 3 ( 2005 ), 358--386. Eamonn Keogh and Chotirat Ann Ratanamahatana. 2005. Exact indexing of dynamic time warping. Knowledge and information systems 7, 3 (2005), 358--386."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Satoshi Koide Chuan Xiao and Yoshiharu Ishikawa. 2020. Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints. (2020).  Satoshi Koide Chuan Xiao and Yoshiharu Ishikawa. 2020. Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints. (2020).","DOI":"10.14778\/3407790.3407818"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"Scalable Data Series Subsequence Matching with ULISSE","volume":"8","author":"Linardi Michele","year":"2020","unstructured":"Michele Linardi and Themis Palpanas . 2020 . Scalable Data Series Subsequence Matching with ULISSE . The VLDB Journal 8 (2020), 1 -- 26 . Michele Linardi and Themis Palpanas. 2020. Scalable Data Series Subsequence Matching with ULISSE. The VLDB Journal 8 (2020), 1--26.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564735"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914837"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339576"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113351"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1978.1163055"},{"key":"e_1_2_1_23_1","first-page":"40","article-title":"Tuning time series queries in finance: Case studies and recommendations","volume":"22","author":"Shasha Dennis","year":"1999","unstructured":"Dennis Shasha . 1999 . Tuning time series queries in finance: Case studies and recommendations . IEEE Data Eng. Bull. 22 , 2 (1999), 40 -- 46 . Dennis Shasha. 1999. Tuning time series queries in finance: Case studies and recommendations. IEEE Data Eng. Bull. 22, 2 (1999), 40--46.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00574-9"},{"key":"e_1_2_1_25_1","unstructured":"T. Sun H. Liu S. Mcloone S. Ji and X. Wu. 2020. Time series indexing by dynamic covering with cross-range constraints. The VLDB Journal (2020) 1--20.  T. Sun H. Liu S. Mcloone S. Ji and X. Wu. 2020. Time series indexing by dynamic covering with cross-range constraints. The VLDB Journal (2020) 1--20."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994784"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-012-0250-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_1_29_1","volume-title":"KV-Match: A Subsequence Matching Approach Supporting Normalization and Time Warping. In 2019 IEEE 35th International Conference on Data Engineering (ICDE).","author":"Wu Jiaye","year":"2019","unstructured":"Jiaye Wu , Peng Wang , Ningting Pan , Chen Wang , Wei Wang , and Jianmin Wang . 2019 . KV-Match: A Subsequence Matching Approach Supporting Normalization and Time Warping. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). Jiaye Wu, Peng Wang, Ningting Pan, Chen Wang, Wei Wang, and Jianmin Wang. 2019. KV-Match: A Subsequence Matching Approach Supporting Normalization and Time Warping. In 2019 IEEE 35th International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.151"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0179"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.79"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872780"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00211"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3523210.3523222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:53:23Z","timestamp":1672224803000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3523210.3523222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":34,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.14778\/3523210.3523222"],"URL":"https:\/\/doi.org\/10.14778\/3523210.3523222","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}