TL;DR
This paper introduces a novel approach using an I/O-conscious skip list data structure to efficiently process forecasting queries over massive time series datasets. By intelligently selecting subsets of historical data and pre-building models, the system significantly speeds up predictions while maintaining accuracy, addressing a key scalability challenge in financial and scientific applications.
What Problem Does This Paper Address?
Many scientific and financial applications rely on analyzing and forecasting time series data (e.g., stock prices, sensor readings). However, the sheer volume of this data often makes direct model building for predictions computationally prohibitive. Traditional methods struggle with the "curse of dimensionality" and the cost of processing vast amounts of historical data. This paper tackles the challenge of efficiently answering forecasting queries over large time series datasets by proposing a method to select an optimal subset of historical data and pre-build predictive models, thereby reducing the computational burden for individual queries.
Methods
The core of the proposed solution lies in an I/O-conscious skip list data structure. Unlike standard in-memory skip lists, this version is optimized for disk storage, replicating keys at each level to facilitate efficient sequential reads. This structure allows for data to be accessed at different granularities, corresponding to different levels of the skip list.
The paper introduces a two-step process for handling forecasting queries:
- Determining Optimal Data Subset: For a given forecast interval, statistical tests of hypotheses are used to determine:
- Proper History Length (h(f)): How far back in time to look for relevant data.
- Number of Data Points (n): How many data points within that history to use for model building. This density (n/h(f)) helps select the appropriate level in the skip list.
- Pre-built Models (PMs): To further accelerate query processing, the authors propose pre-building a set of "models" (e.g., regression coefficients) for common forecast intervals. A randomized algorithm, ChoosePMSet, selects which models to pre-build, balancing the cost of maintaining these models against the benefit of faster query answering. This is analogous to materialized views but for predictive models.
Query processing then involves selecting the closest pre-built model to the query's forecast interval. For complex queries like range aggregations and joins, the paper leverages the monotonicity assumption (longer forecast intervals imply longer histories and sparser data) and the pre-built models to avoid materializing future data points.
Datasets
The empirical evaluation was conducted on two real-world stock price datasets:
- IBM stock price history: January 3rd, 1966 to October 10th, 2007 (per second tick data, over 1 GB).
- McDonald's stock price history: January 2nd, 1970 to October 10th, 2007 (per second tick data, almost 1 GB).
The experiments simulated a "now" point one year prior to the end of the dataset to allow for forecasting and verification against actual future data.
Key Insights and Ideas
- Data Granularity Matters: Not all historical data is equally useful for forecasting. The paper demonstrates that selecting an appropriate history length and data density is crucial for both prediction accuracy and computational efficiency.
- Skip Lists as a Foundation: The I/O-conscious skip list provides a flexible and efficient data structure for accessing time series data at various granularities, supporting search, interpolation, and serving as a basis for model building.
- Pre-built Models (PMs) for Speed: Materializing predictive models (PMs) instead of raw data offers a significant speedup for forecasting queries, especially when combined with a cost-aware selection strategy.
- Monotonicity Assumption: The assumption that forecast interval length correlates with history length and data sparsity is empirically validated and enables efficient processing of complex queries.
- Trade-off Management: The ChoosePMSet algorithm provides a principled way to manage the trade-off between the cost of maintaining pre-built models and the desired level of query performance and accuracy.
Key Results
- Accuracy: The skip-list approach generally maintained prediction accuracy comparable to or better than building models on-the-fly, especially for longer forecast intervals where direct methods struggled due to data limitations. Using a sufficient number of PMs (e.g., 10-20) yielded accuracy close to building models on-the-fly.
- Speed: Query execution time was dramatically reduced by using pre-built models. For longer forecast intervals (e.g., one month or more), the skip-list approach was orders of magnitude faster than building models on-the-fly, which became prohibitively slow.
- Model Distance vs. Error: The theoretical metric of "model distance" (how well a query interval is covered by pre-built models) correlated well with actual prediction error, validating the effectiveness of the ChoosePMSet algorithm.
- Monotonicity: The skip list level used for prediction was shown to increase monotonically with the forecast interval, supporting the assumption used for complex query processing.
- Stability: Using a larger set of PMs (e.g., 10) resulted in more stable query results (lower variance) compared to using fewer PMs (e.g., 4).
Limitations and Future Work
- Model Types: The paper primarily uses multiple regression models. Future work could explore the effectiveness of the approach with other forecasting models.
- Multiple Time Series: The current work focuses on single time series. Extending the techniques to handle multiple, potentially correlated time series is a promising direction.
- Visualization Tools: The authors suggest developing visualization tools to help users understand the data and interact with the model space, which would enhance the practical usability of the system.
- Workload Dynamics: While the ChoosePMSet algorithm uses a workload PMF, adapting to dynamically changing workloads or exploring more robust methods for workload estimation could be beneficial.
Summary updated