Time Series Data Cleaning: A Survey <s> III. CONSTRAINT BASED CLEANING ALGORITHM <s> The recently introduced notion of order dependency in the relational model is generalized to include situations where order dependency is satisfied in an approximate way. Two fundamental types of approximate satisfaction are distinguished and analyzed. It is shown for both types that such approximate satisfaction of order dependencies can be applied to substantially reduce indexing space without significantly increasing access time. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> III. CONSTRAINT BASED CLEANING ALGORITHM <s> We study sequential dependencies that express the semantics of data with ordered domains and help identify quality problems with such data. Given an interval g, we write X →g Y to denote that the difference between the Y -attribute values of any two consecutive records, when sorted on X, must be in g. For example, time →(0,∞) sequence_number indicates that sequence numbers are strictly increasing over time, whereas sequence_number →[4, 5] time means that the time "gaps" between consecutive sequence numbers are between 4 and 5. Sequential dependencies express relationships between ordered attributes, and identify missing (gaps too large), extraneous (gaps too small) and out-of-order data. ::: ::: To make sequential dependencies applicable to real-world data, we relax their requirements and allow them to hold approximately (with some exceptions) and conditionally (on various subsets of the data). This paper proposes the notion of conditional approximate sequential dependencies and provides an efficient framework for discovering pattern tableaux, which are compact representations of the subsets of the data (i.e., ranges of values of the ordered attributes) that satisfy the underlying dependency. We present analyses of our proposed algorithms, and experiments on real data demonstrating the efficiency and utility of our framework. <s> BIB002 </s> Time Series Data Cleaning: A Survey <s> III. CONSTRAINT BASED CLEANING ALGORITHM <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> BIB003
In this section, we introduce several typical algorithms, which include order dependencies (ODs) BIB001 , sequential dependencies (SDs) BIB002 and speed constraints BIB003 , for repairing time series errors.