Seasonal-trend decomposition is one of the most fundamental concepts in time series analysis that supports various downstream tasks, including time series anomaly detection and forecasting. However, existing decomposition methods rely on batch processing with a time complexity of O(W), where W is the number of data points within a time window. Therefore, they cannot always efficiently support real-time analysis that demands low processing delay. To address this challenge, we propose OneShotSTL, an efficient and accurate algorithm that can decompose time series online with an update time complexity of O(1). OneShotSTL is more than $1,000$ times faster than the batch methods, with accuracy comparable to the best counterparts. Extensive experiments on real-world benchmark datasets for downstream time series anomaly detection and forecasting tasks demonstrate that OneShotSTL is from 10 to over 1,000 times faster than the state-of-the-art methods, while still providing comparable or even better accuracy.

翻译：季节趋势分解是时间序列分析中最基础的概念之一，支持各种下游任务，包括时序异常检测和预测。然而，现有的分解方法依赖于批量处理，时间复杂度为O(W)，其中W是时间窗口内的数据点数。因此，它们不能始终有效地支持需要低处理延迟的实时分析。为了应对这一挑战，我们提出了一种高效准确的算法OneShotSTL，它可以在线分解时间序列，更新时间复杂度为O(1)。OneShotSTL比批量方法快1000多倍，准确性可与最佳对手相媲美。在针对下游时序异常检测和预测任务的实际基准数据集上进行的大量实验表明，OneShotSTL比最先进的方法快10到1000倍，同时仍提供可比甚至更好的准确性。