T-Rex: Optimizing Pattern Search on Time Series
Open Access
- 13 June 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (2) , 1-26
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Efficient processing of window functions in analytical SQL queriesProceedings of the VLDB Endowment, 2015
- TrillProceedings of the VLDB Endowment, 2014
- Efficient event pattern matching with match windows2012
- High-performance dynamic pattern matching over disordered streamsProceedings of the VLDB Endowment, 2010
- Stock time series pattern matching: Template-based vs. rule-based approachesEngineering Applications of Artificial Intelligence, 2007
- Expressing and optimizing sequence queries in database systemsACM Transactions on Database Systems, 2004
- Resource Sharing in Continuous Sliding-Window Aggregates2004
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002
- Power of the Mann–Kendall and Spearman's rho tests for detecting monotonic trends in hydrological seriesJournal of Hydrology, 2002
- Volcano-an extensible and parallel query evaluation systemIEEE Transactions on Knowledge and Data Engineering, 1994