Time Series Data Cleaning: A Survey <s> C. SPEED CONSTRAINTS <s> Many statistical models, and in particular autoregressive-moving average time series models, can be regarded as means of transforming the data to white noise, that is, to an uncorrelated sequence of errors. If the parameters are known exactly, this random sequence can be computed directly from the observations; when this calculation is made with estimates substituted for the true parameter values, the resulting sequence is referred to as the "residuals," which can be regarded as estimates of the errors. If the appropriate model has been chosen, there will be zero autocorrelation in the errors. In checking adequacy of fit it is therefore logical to study the sample autocorrelation function of the residuals. For large samples the residuals from a correctly fitted model resemble very closely the true errors of the process; however, care is needed in interpreting the serial correlations of the residuals. It is shown here that the residual autocorrelations are to a close approximation representable as a singular linear transformation of the autocorrelations of the errors so that they possess a singular normal distribution. Failing to allow for this results in a tendency to overlook evidence of lack of fit. Tests of fit and diagnostic checks are devised which take these facts into account. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> C. SPEED CONSTRAINTS <s> Stream data are often dirty, for example, owing to unreliable sensor reading, or erroneous extraction of stock prices. Most stream data cleaning approaches employ a smoothing filter, which may seriously alter the data without preserving the original information. We argue that the cleaning should avoid changing those originally correct/clean data, a.k.a. the minimum change principle in data cleaning. To capture the knowledge about what is clean, we consider the (widely existing) constraints on the speed of data changes, such as fuel consumption per hour, or daily limit of stock prices. Guided by these semantic constraints, in this paper, we propose SCREEN, the first constraint-based approach for cleaning stream data. It is notable that existing data repair techniques clean (a sequence of) data as a whole and fail to support stream computation. To this end, we have to relax the global optimum over the entire sequence to the local optimum in a window. Rather than the commonly observed NP-hardness of general data repairing problems, our major contributions include: (1) polynomial time algorithm for global optimum, (2) linear time algorithm towards local optimum under an efficient Median Principle,(3) support on out-of-order arrivals of data points, and(4) adaptive window size for balancing repair accuracy and efficiency. Experiments on real datasets demonstrate that SCREEN can show significantly higher repair accuracy than the existing approaches such as smoothing. <s> BIB002 </s> Time Series Data Cleaning: A Survey <s> C. SPEED CONSTRAINTS <s> A time series is a series of data points indexed (or listed or graphed) in time order. Errors are prevalent in time series, such as GPS trajectories or sensor readings. The quality of the time series greatly influences the authenticity and confidence of other operations. Existing methods on cleaning sequential data employ a constraint on value changing speeds and perform constraint-based or statistics-based repairing. However, such speed-based methods are difficult to identify and repair outliers, which does not significantly deviate from the true value and does satisfy the speed constraint. And such a statistics-based method is not perfect in terms of efficiency and accuracy. To handle such problem of time series cleaning, in this paper, we propose a first variance-based approach for cleaning time series. In order to support the stream computation, we consider the data in a window as a whole and adopt the idea of sliding window to solve the problem in stream computation. <s> BIB003
To clean time series data, speed constraint-based method proposed by Song et al. BIB002 consider the restrictions of speed on value changes in a given interval. As we have learned some common sense, e.g., the maximum flying speed of a bird, temperatures in a day, car mileage, etc. Consider with time window T is a pair of minimum speed S min and maximum speed S max over the time series x = x 1 , x 2 , . . . , x t , where each x i is the value of the i-th data point, with a timestamp i. For instance, consider time series: = 90 > 50 are violations to s max = 50. To remedy the violations (denoted by red lines), a repair on x 5 can be performed, i.e., x 5 = 190, which is represented by the blue '' * '' symbol in Figure 3 . As illustrated in Figure 3 , the repaired sequence satisfies both the maximum and minimum speed constraints. Generally, a speed constraint is in the form of equation BIB001 . If time series data x satisfies the speed constraint S, then for any x i , x j in a time window T , it has S min < In practical applications, speed constraints are often valid for a specific period of time. For instance, when considering the fastest speed of a car, the time period of the reference is often in hours, and two data points in different years are not considered. The value of the speed constraints S may be positive (the growth rate of the constraint value) or negative (the rate of decline of the constraint value). Speed constraints are less effective when dealing with small errors, and Yin et al. BIB003 propose a further study of variance constraints, which use the variance threshold V to measure the degree of dispersion of the time series in a given W window.