Time series often present gaps in the data. This phenomenon, also called missing values, is so prevalent that a cottage industry of missing-value imputation algorithms exists, each with different capabilities and efficacy/efficiency tradeoffs. So far, however, there has been no way to accurately select the most appropriate approach among all algorithms, given a new time series requiring imputation. In this paper, we introduce a new configuration-free system, A-DARTS (for Automated DAta Repair in Time Series), to automatically select the best imputation technique for a given faulty time series. A-DARTS's recommendation engine is trained via an iterative process that carefully learns the behavior of imputation algorithms using an extensive dataset of time series that we curated. The selection process is made efficient by several new pruning techniques particularly adjusted to time series data. Applications that manipulate time series can now easily embed A-DARTS's recommendation engine and impute data on the fly. Our experiments show that our system picks, on average, the best imputation algorithm 20% more frequently than the best-in-class AutoML technique. Moreover, it produces stable recommendations across datasets by incurring 2.5x less error variance, eliminating the stability issue observed in all state-of-the-art methods we tested.

With the emergence of the Internet of Things (IoT), time series streams have become ubiquitous in our daily life. Recording such data is rarely a perfect process, as sensor failures frequently occur, yielding occasional blocks of data that go missing in multiple time series. These missing blocks do not only affect real-time monitoring but also compromise the quality of online data analyses. Effective streaming recovery (imputation) techniques either have a quadratic runtime complexity, which is infeasible for any moderately sized data, or cannot recover more than one time series at a time. In this paper, we introduce a new online recovery technique to recover multiple time series streams in linear time. Our recovery technique implements a novel incremental version of the Centroid Decomposition technique and reduces its complexity from quadratic to linear. Using this incremental technique, missing blocks are efficiently recovered in a continuous manner based on previous recoveries. We formally prove the correctness of our new incremental computation, which yields an accurate recovery. Our experimental results on real-world time series show that our recovery technique is, on average, 30% more accurate than the state of the art while being vastly more efficient.

Recording sensor data is seldom a perfect process. Failures in power, communication or storage can leave occasional blocks of data missing, affecting not only real-time monitoring but also compromising the quality of near- and off-line data analysis. Several recovery (imputation) algorithms have been proposed to replace missing blocks. Unfortunately, little is known about their relative performance, as existing comparisons are limited to either a small subset of relevant algorithms or to very few datasets or often both. Drawing general conclusions in this case remains a challenge. In this paper, we empirically compare twelve recovery algorithms using a novel benchmark. All but two of the algorithms were re-implemented in a uniform test environment. The benchmark gathers ten different datasets, which collectively represent a broad range of applications. Our benchmark allows us to fairly evaluate the strengths and weaknesses of each approach, and to recommend the best technique on a use-case basis. It also allows us to identify the limitations of the current body of algorithms and suggest future research directions.