{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T22:32:27Z","timestamp":1769985147390,"version":"3.49.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Pattern search is an important class of queries for time series data. Time series patterns often match variable-length segments with a large search space, thereby posing a significant performance challenge. The existing pattern search systems, for example, SQL query engines supporting MATCH_RECOGNIZE, are ineffective in pruning the large search space of variable-length segments. In many cases, the issue is due to the use of a restrictive query language modeled on time series points and a computational model that limits search space pruning. We built T-ReX to address this problem using two main building blocks: first, a MATCH_RECOGNIZE language extension that exposes the notion of segment variable and adds new operators, lending itself to better optimization; second, an executor capable of pruning the search space of matches and minimizing total query time using an optimizer. We conducted experiments using 5 real-world datasets and 11 query templates, including those from existing works. T-ReX outperformed an optimized NFA-based pattern search executor by 6x in median query time and an optimized tree-based executor by 19X.<\/jats:p>","DOI":"10.1145\/3589275","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-26","source":"Crossref","is-referenced-by-count":14,"title":["T-Rex: Optimizing Pattern Search on Time Series"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5291-0167","authenticated-orcid":false,"given":"Silu","family":"Huang","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3326-1790","authenticated-orcid":false,"given":"Erkang","family":"Zhu","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8252-5270","authenticated-orcid":false,"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2119-3230","authenticated-orcid":false,"given":"Leonhard","family":"Spiegelberg","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"https:\/\/github.com\/CSSEGISandData\/COVID-19\/tree\/master\/archived_data\/archived_time_series","author":"Covid-19 data repository by the center for systems science and engineering (csse) at Johns Hopkins University","year":"2021","unstructured":"Covid-19 data repository by the center for systems science and engineering (csse) at Johns Hopkins University. https:\/\/github.com\/CSSEGISandData\/COVID-19\/tree\/master\/archived_data\/archived_time_series, 2021."},{"key":"e_1_2_2_2_1","volume-title":"https:\/\/en.wikipedia.org\/wiki\/Cold_wave","author":"Wave Cold","year":"2022","unstructured":"Cold Wave. https:\/\/en.wikipedia.org\/wiki\/Cold_wave, 2022."},{"key":"e_1_2_2_3_1","volume-title":"https:\/\/math.stackexchange.com\/questions\/195245\/average-distance-between-random-points-on-a-line-segment","author":"Between Random Expected Distance","year":"2022","unstructured":"Expected Distance Between Random Points on a Line Segment. https:\/\/math.stackexchange.com\/questions\/195245\/average-distance-between-random-points-on-a-line-segment, 2022."},{"key":"e_1_2_2_4_1","volume-title":"https:\/\/math.stackexchange.com\/a\/72351","author":"Distinct Expected Number","year":"2022","unstructured":"Expected Number of Distinct Items from a Multi-Set. https:\/\/math.stackexchange.com\/a\/72351, 2022."},{"key":"e_1_2_2_5_1","volume-title":"https:\/\/www.kaggle.com\/selfishgene\/historical-hourly-weather-data","author":"Historical","year":"2022","unstructured":"Historical hourly weather data 2012--2017. https:\/\/www.kaggle.com\/selfishgene\/historical-hourly-weather-data, 2022."},{"key":"e_1_2_2_6_1","volume-title":"TR 19075--5:2016 Information technology -- Database languages -- SQL Technical Reports -- Part 5: Row Pattern Recognition in SQL. https:\/\/www.iso.org\/standard\/65143","year":"2022","unstructured":"ISO\/IEC TR 19075--5:2016 Information technology -- Database languages -- SQL Technical Reports -- Part 5: Row Pattern Recognition in SQL. https:\/\/www.iso.org\/standard\/65143.html, 2022."},{"key":"e_1_2_2_7_1","volume-title":"https:\/\/trino.io\/docs\/current\/sql\/match-recognize.html","author":"RECOGNIZE.","year":"2022","unstructured":"MATCH_RECOGNIZE. https:\/\/trino.io\/docs\/current\/sql\/match-recognize.html, 2022."},{"key":"e_1_2_2_8_1","volume-title":"https:\/\/docs.snowflake.com\/en\/sql-reference\/constructs\/match_recognize.html","author":"Snowflake Documentation RECOGNIZE","year":"2022","unstructured":"MATCH_RECOGNIZE - Snowflake Documentation. https:\/\/docs.snowflake.com\/en\/sql-reference\/constructs\/match_recognize.html, 2022."},{"key":"e_1_2_2_9_1","volume-title":"https:\/\/docs.oracle.com\/en\/middleware\/fusion-middleware\/osa\/19.1\/cqlreference\/pattern-recognition-match_recognize.html","author":"Pattern Recognition RECOGNIZE","year":"2022","unstructured":"MATCH_RECOGNIZE for Pattern Recognition. https:\/\/docs.oracle.com\/en\/middleware\/fusion-middleware\/osa\/19.1\/cqlreference\/pattern-recognition-match_recognize.html, 2022."},{"key":"e_1_2_2_10_1","volume-title":"https:\/\/nightlies.apache.org\/flink\/flink-docs-release-1.14\/docs\/dev\/table\/sql\/queries\/match_recognize\/","author":"Pattern Recognition RECOGNIZE","year":"2022","unstructured":"MATCH_RECOGNIZE for Pattern Recognition. https:\/\/nightlies.apache.org\/flink\/flink-docs-release-1.14\/docs\/dev\/table\/sql\/queries\/match_recognize\/, 2022."},{"key":"e_1_2_2_11_1","volume-title":"https:\/\/docs.microsoft.com\/en-us\/stream-analytics-query\/match-recognize-stream-analytics","author":"Stream RECOGNIZE","year":"2022","unstructured":"MATCH_RECOGNIZE (Stream Analytics). https:\/\/docs.microsoft.com\/en-us\/stream-analytics-query\/match-recognize-stream-analytics, 2022."},{"key":"e_1_2_2_12_1","volume-title":"https:\/\/github.com\/numenta\/NAB\/tree\/master\/data\/realKnownCause","author":"The","year":"2022","unstructured":"The numenta anomaly benchmark (nab). https:\/\/github.com\/numenta\/NAB\/tree\/master\/data\/realKnownCause, 2022."},{"key":"e_1_2_2_13_1","volume-title":"https:\/\/livenewcapital.com\/snowflake-match_recognize-for-finding-transactions-that-do-not-match-a-pattern\/","author":"Snowflake","year":"2023","unstructured":"Snowflake MATCH_RECOGNIZE for finding transactions that do NOT match a pattern. https:\/\/livenewcapital.com\/snowflake-match_recognize-for-finding-transactions-that-do-not-match-a-pattern\/, 2023."},{"key":"e_1_2_2_14_1","volume-title":"https:\/\/livenewcapital.com\/match_recognize-for-performing-a-b-analysis\/","author":"Snowflake","year":"2023","unstructured":"Snowflake MATCH_RECOGNIZE for performing A\/B analysis on streaming data. https:\/\/livenewcapital.com\/match_recognize-for-performing-a-b-analysis\/, 2023."},{"key":"e_1_2_2_15_1","volume-title":"Optimizing Pattern Search on Time Series (Extended Version). https:\/\/www.microsoft.com\/en-us\/research\/publication\/t-rex-optimizing-pattern-search-on-time-series-extended-version\/","year":"2023","unstructured":"T-ReX: Optimizing Pattern Search on Time Series (Extended Version). https:\/\/www.microsoft.com\/en-us\/research\/publication\/t-rex-optimizing-pattern-search-on-time-series-extended-version\/, 2023."},{"key":"e_1_2_2_16_1","volume-title":"https:\/\/research.redhat.com\/blog\/research_project\/complex-event-processing-2\/ https:\/\/github.com\/ilya-kolchinsky\/OpenCEP","author":"Schuster Ilya","year":"2021","unstructured":"Kolchinsky, Ilya and Schuster, Assaf. OpenCEP. https:\/\/research.redhat.com\/blog\/research_project\/complex-event-processing-2\/ https:\/\/github.com\/ilya-kolchinsky\/OpenCEP, 2021."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376634"},{"key":"e_1_2_2_18_1","first-page":"502","volume-title":"Querying shapes of histories","author":"Agrawal R.","year":"1995","unstructured":"R. Agrawal, G. Psaila, E. L. Wimmers, and M. Za\u00eft. Querying shapes of histories. In U. Dayal, P. M. D. Gray, and S. Nishio, editors, VLDB'95, Proceedings of 21th Int'l Conf. on Very Large Data Bases, September 11--15, 1995, Zurich, Switzerland, pages 502--514. Morgan Kaufmann, 1995."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469-8.50032-2"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.587537"},{"key":"e_1_2_2_21_1","first-page":"33","volume-title":"EDBT 2011, 14th Int'l Conf. on Extending Database Technology, Uppsala, Sweden, March 21--24, 2011","author":"Cadonna B.","year":"2011","unstructured":"B. Cadonna, J. Gamper, and M. H. B\u00f6hlen. Sequenced event set pattern matching. In A. Ailamaki, S. Amer-Yahia, J. M. Patel, T. Risch, P. Senellart, and J. Stoyanovich, editors, EDBT 2011, 14th Int'l Conf. on Extending Database Technology, Uppsala, Sweden, March 21--24, 2011, Proceedings, pages 33--44. ACM, 2011."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339607"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735503"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920873"},{"key":"e_1_2_2_25_1","first-page":"412","volume-title":"Third Biennial Conf. on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7--10, 2007, Online Proceedings","author":"Demers A. J.","year":"2007","unstructured":"A. J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. M. White. Cayuga: A general purpose event monitoring system. In Third Biennial Conf. on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7--10, 2007, Online Proceedings, pages 412--422. www.cidrdb.org, 2007."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2006.07.003"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/582415.582418"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236190"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236189"},{"key":"e_1_2_2_32_1","first-page":"589","volume-title":"Proceedings of the 2019 Int'l Conf. on Management of Data, SIGMOD Conf. 2019","author":"Kolchinsky I.","year":"2019","unstructured":"I. Kolchinsky and A. Schuster. Real-time multi-pattern detection over event streams. In P. A. Boncz, S. Manegold, A. Ailamaki, A. Deshpande, and T. Kraska, editors, Proceedings of the 2019 Int'l Conf. on Management of Data, SIGMOD Conf. 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 589--606. ACM, 2019."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2675743.2771832"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794375"},{"key":"e_1_2_2_35_1","first-page":"14","volume-title":"Proceedings of the 7th Workshop on Data Management for Sensor Networks, in conjunction with VLDB, DMSN 2010, Singapore, September 13, 2010, ACM Int'l Conf. Proceeding Series","author":"Liu M.","year":"2010","unstructured":"M. Liu, M. Ray, E. A. Rundensteiner, D. J. Dougherty, C. Gupta, S. Wang, I. Ari, and A. Mehta. Processing nested complex sequence pattern queries over event streams. In D. Zeinalipour-Yazti and W. Lee, editors, Proceedings of the 7th Workshop on Data Management for Sensor Networks, in conjunction with VLDB, DMSN 2010, Singapore, September 13, 2010, ACM Int'l Conf. Proceeding Series, pages 14--19. ACM, 2010."},{"key":"e_1_2_2_36_1","first-page":"388","volume-title":"Proceedings of the 2018 CHI Conf. on Human Factors in Computing Systems, CHI 2018, Montreal, QC, Canada, April 21--26","author":"Mannino M.","year":"2018","unstructured":"M. Mannino and A. Abouzied. Expressive time series querying with hand-drawn scale-free sketches. In R. L. Mandryk, M. Hancock, M. Perry, and A. L. Cox, editors, Proceedings of the 2018 CHI Conf. on Human Factors in Computing Systems, CHI 2018, Montreal, QC, Canada, April 21--26, 2018, page 388. ACM, 2018."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559867"},{"key":"e_1_2_2_38_1","first-page":"495","volume-title":"Proceedings of the 2016 Int'l Conf. on Management of Data, SIGMOD Conf. 2016","author":"Ray M.","year":"2016","unstructured":"M. Ray, C. Lei, and E. A. Rundensteiner. Scalable pattern sharing on event streams. In F. \u00d6zcan, G. Koutrika, and S. Madden, editors, Proceedings of the 2016 Int'l Conf. on Management of Data, SIGMOD Conf. 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 495--510. ACM, 2016."},{"key":"e_1_2_2_39_1","first-page":"525","volume-title":"Joint 2013 EDBT\/ICDT Conf., EDBT '13 Proceedings","author":"Ray M.","year":"2013","unstructured":"M. Ray, E. A. Rundensteiner, M. Liu, C. Gupta, S. Wang, and I. Ari. High-performance complex event processing using continuous sliding views. In G. Guerrini and N. W. Paton, editors, Joint 2013 EDBT\/ICDT Conf., EDBT '13 Proceedings, Genoa, Italy, March 18--22, 2013, pages 525--536. ACM, 2013."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005568"},{"key":"e_1_2_2_41_1","first-page":"51","volume-title":"Proceedings of the 2020 Int'l Conf. on Management of Data, SIGMOD Conf. 2020, online Conf. [Portland, OR, USA], June 14--19, 2020","author":"Siddiqui T.","year":"2020","unstructured":"T. Siddiqui, P. Luh, Z. Wang, K. Karahalios, and A. G. Parameswaran. Shapesearch: A flexible and efficient system for shape-based exploration of trendlines. In D. Maier, R. Pottinger, A. Doan, W. Tan, A. Alawini, and H. Q. Ngo, editors, Proceedings of the 2020 Int'l Conf. on Management of Data, SIGMOD Conf. 2020, online Conf. [Portland, OR, USA], June 14--19, 2020, pages 51--65. ACM, 2020."},{"key":"e_1_2_2_42_1","first-page":"1243","volume-title":"SIGMOD '22: Int'l Conf. on Management of Data","author":"Vogelsgesang A.","year":"2022","unstructured":"A. Vogelsgesang, T. Neumann, V. Leis, and A. Kemper. Efficient evaluation of arbitrarily-framed holistic SQL aggregates and window functions. In Z. Ives, A. Bonifati, and A. E. Abbadi, editors, SIGMOD '22: Int'l Conf. on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 1243--1256. ACM, 2022."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994537"},{"key":"e_1_2_2_44_1","first-page":"407","volume-title":"Proceedings of the ACM SIGMOD Int'l Conf. on Management of Data","author":"Wu E.","year":"2006","unstructured":"E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In S. Chaudhuri, V. Hristidis, and N. Polyzotis, editors, Proceedings of the ACM SIGMOD Int'l Conf. on Management of Data, Chicago, Illinois, USA, June 27--29, 2006, pages 407--418. ACM, 2006."},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of the 17th Int'l Conf. on Data Engineering, April 2--6, 2001","author":"Yang J.","year":"2001","unstructured":"J. Yang and J. Widom. Incremental computation and maintenance of temporal aggregates. In D. Georgakopoulos and A. Buchmann, editors, Proceedings of the 17th Int'l Conf. on Data Engineering, April 2--6, 2001, Heidelberg, Germany, pages 51--60. IEEE Computer Society, 2001."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-1694(01)00594-7"},{"key":"e_1_2_2_47_1","first-page":"217","volume-title":"SIGMOD 2014","author":"Zhang H.","year":"2014","unstructured":"H. Zhang, Y. Diao, and N. Immerman. On complexity and optimization of expensive queries in complex event processing. In C. E. Dyreson, F. Li, and M. T. \u00d6zsu, editors, Int'l Conf. on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22--27, 2014, pages 217--228. ACM, 2014."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589275","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589275"],"URL":"https:\/\/doi.org\/10.1145\/3589275","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}