Missing values often occur in multivariate time series, affecting data analysis and applications. Existing studies typically use complete data to train imputation models, which are then used to fill missing values. However, in practice, missing values could appear in various cells. Such varieties unfortunately prevent imputation models performing, even making fillings unavailable without the convergence guarantee, i.e., lacking the ensurance of obtaining the optimal solution when the iteration tends to infinite. The reasons are that (1) the imputed values of multiple cells could affect each other towards the conformance to models, and (2) dependencies obtained from complete data may not be accurate enough to impute many unobserved values, which poses a tougher challenge of the convergence. In this work, we study the collaborative imputation with the convergence guarantee. By “collaborative”, we mean (1) all the missing cells can be collaboratively imputed with the guaranteed conformance to models, and (2) the imputation models are collaboratively optimized according to fillings as well. Our major technical highlights include 1) introducing the statistically explainable collaborative imputation via likelihood maximization, 2) designing a collaborative imputation algorithm for multiple missing cells and extending it into a parallel version equivalently, 3) improving the algorithm by both imputation values and models collaboratively optimized with the convergence guarantee in parallel, 4) designing the streaming imputation and adaptive parameter determination strategies. Experiments on real incomplete datasets demonstrate the superiority of our methods against twelve baselines, in both imputation accuracy and downstream applications.

Abstract Relational data play a crucial role in various fields, but they are often plagued by low-quality issues such as erroneous and missing values, which can terribly impact downstream applications. To tackle these issues, relational data cleaning with traditional signals, e.g., statistics, constraints, and clusters, have been extensively studied, with interpretability and efficiency. Recently, considering the strong capability of modeling complex relationships, artificial intelligence (AI) techniques have been introduced into the data cleaning field. These AI-based methods either consider multiple cleaning signals, integrate various techniques into the cleaning system, or incorporate neural networks. Among them, methods utilizing deep neural networks are classified as deep learning (DL) based, while those that do not are classified as machine learning (ML) based. In this study, we focus on three essential tasks (i.e., error detection, data repairing, and data imputation) for cleaning relational data, to comprehensively review the representative methods using traditional or AI techniques. By comparing and analyzing two types of methods across five dimensions (cost, generalization, interpretability, efficiency, and effectiveness), we provide insights into their strengths, weaknesses, and suitable application scenarios. Finally, we analyze the challenges and open issues currently faced in data cleaning and discuss possible directions for future studies.

Spatio-temporal data collected from geographically distributed sources often contain dirty values that affect downstream applications. Temporal data repairing methods, e.g., based on speed constraints, may mistakenly treat sudden changes as errors, although they represent real events and occur simultaneously at multiple locations. Spatial data repairing approaches emphasize value consistency across different locations but ignore temporal pattern similarity. Meanwhile, existing spatio-temporal repairing methods focus more on spatial error correction rather than temporal value repairing across locations. Therefore, we use both temporal and spatial dependencies to identify and repair spatio-temporal errors. Our main contributions are: (1) formalizing the optimal spatio-temporal data repairing problem under constraints and proving its NP-hardness; (2) designing an exact algorithm that decomposes global repair into local decisions with pruning methods; (3) developing two approximate algorithms with theoretical guarantees and probabilities of hitting the optimal solution, where the first explores a wider search space for higher accuracy, and the second uses a greedy sliding-window strategy to improve efficiency; and (4) conducting experiments on nine real-world datasets and downstream applications against eleven baselines, which demonstrate the superiority and practicability of our methods.

Dirty data are often observed in the multivariate time series, which not only degrades data quality but also adversely affects various downstream applications. Existing studies typically focus on repairing such errors appearing in either timestamps or attribute values alone, relying on the assumption that the other part is clean. However, in real scenarios, owing to various reasons, both timestamps and attribute values can be erroneous. It is intuitive to repair timestamps and attribute values respectively by calling different methods in turn. However, such a strategy may lead to over-repairing and introduce additional errors, by ignoring the mutual reference between timestamps and attribute values. Therefore, in this study, rather than repairing timestamps and attribute values respectively by calling different methods in turn, we consider the repairing for both attribute values and timestamps simultaneously. Our major contributions include (1) defining the multivariate speed constraints and formalizing the optimal repair problem with the NP-hardness analysis, (2) computing the exact solutions with pruning strategies and correctness ensurance, (3) designing the quadratic time approximation algorithm with the performance guarantee, (4) devising the linear time algorithm and ensuring its approximation performance bound. Empirical results over real-world dirty datasets demonstrate the superiority and practicality of our algorithms, against eleven competing methods, where our algorithm not only achieves the best accuracy but also spends the lowest time cost.

High-quality data are crucial for practical applications, but obtaining them through high-precision sensors comes at a high cost. To guarantee the trade-off between cost and precision, we may use multiple low-precision sensors to obtain the nearly accurate data fusion results at an affordable cost. The commonly used techniques, such as the Kalman filter and truth discovery methods, typically compute fusion values by combining all the observations according to predictions or sensor reliability. However, low-precision sensors can often cause outliers, and such methods combining all observations are susceptible to interference. To handle this problem, we select a single observation from multiple sensor readings as the fusion result for each timestamp. The selection strategy is guided by the maximum likelihood estimation, to determine the most probable changing trends of fusion results with adjacent timestamps. Our major contributions include (1) the problem formalization and NP-hardness analysis on finding the fusion result with the maximum likelihood w.r.t. local fusion models, (2) exact algorithms based on dynamic programming for tackling the problem, (3) efficient approximation methods with performance guarantees. Experiments on various real datasets and downstream applications demonstrate the superiority and practicality of our work in low-precision sensor data fusion.

Although clustering methods have shown promising performance in various applications, they cannot effectively handle incomplete data. Existing studies often impute missing values first before clustering analysis and conduct these two processes separately. However, inaccurate imputation does not necessarily contribute positively to the subsequent clustering. Intuitively, accurate imputation and clustering can serve and benefit from each other, where clustering-based imputation methods typically utilize cluster signals to impute incomplete data and accurate fillings are expected to bring more valuable data for clustering. Therefore, in this manuscript, rather than considering two tasks independently or conducting them respectively, we study simultaneous clustering and imputing over incomplete data. The immediate benefit is that such a strategy improves both clustering and imputation performance simultaneously, to get a win-win result. Our major technical highlights include (1) the problem formalization and NP-hardness analysis on computing simultaneous clustering and imputing results, (2) exact solutions by transforming the problem as the integer linear programming (ILP) formulation, and (3) efficient approximation algorithms based on the linear programming (LP) relaxation and local neighbors (LN) solution, with approximation guarantees. Experiments on various real-world datasets demonstrate the superiority of our work in clustering and imputing incomplete data.

Dirty data are commonly observed in real applications, making cleaning them a key step in data preparation. The widely adopted idea of cleaning dirty data is based on detecting conflicts w.r.t. integrity constraints. Typical S-repair methods remove a minimal set of tuples (to avoid excessive removal and information loss) such that integrity constraints are no longer violated in remaining tuples. Unfortunately, multiple candidates of minimal removal sets may exist and are difficult to determine which one is indeed proper. We intuitively notice that a clean tuple often has more close neighbors (i.e., higher density) than dirty tuples. Hence, in this paper, we study the problem of finding the optimal S-repair under integrity constraints with the highest density, among various minimal removal sets. Our major contributions include (1) thenp-hardness analysis on solving the problem, (2) a heuristic algorithm for efficiently tackling the problem and returning the optimal solution in certain cases, (3) an approximation performance bounded method with the same optimal solution guarantee. Experiments on real datasets collected from industry with real-world errors demonstrate the superiority of our work in cleaning dirty tuples.

Replicas of the same data item often exhibit varying consistency levels when executing read and write requests due to system availability and network limitations. When one or more replicas respond to a query, estimating the currency (or staleness) of the returned data item (without accessing the other replicas) is essential for applications requiring timely data. Depending on how confident the estimation is, the query may dynamically decide to return the retrieved replicas, or wait for the remaining replicas to respond. The replica currency estimation is expected to be accurate and extremely time efficient without introducing large overhead during query processing. In this paper, we provide theoretical bounds on the confidence of replica currency estimation. Our system computes with a minimum probability p, whether the retrieved replicas are current or stale. Using this confidence-bounded replica currency estimation, we implement a novel DYNAMIC read consistency level in the open-source, NoSQL database, Cassandra. Experiments show that the proposed replica currency estimation is intuitive and efficient. In most tested scenarios, with various query loads and cluster configurations, we show our estimations with confidence levels of at least 0.99 while keeping query latency low (close to reading ONE replica). Moreover, the overheads introduced due to estimation scoring and training are low, incurring only 0.76% to 1.17% of the query processing and replica synchronization time costs, respectively.

To clean dirty data, integrity constraints are often employed. A typical S-repair model removes a minimal set of tuples (to avoid excessive removal and information loss) such that the integrity constraints are no longer violated in the remaining tuples. However, multiple candidates of minimal removal sets exist and are difficult to determine. We intuitively notice that a clean tuple often has more close neighbors (i.e., higher density) than dirty tuples. In this sense, our study proposes to return the S-repair under integrity constraints with the highest density, among various minimal removal sets. We explicitly analyze the hardness of maximizing S-repair density under integrity constraints, together with efficient approximation. Extensive experiments over real datasets collected from industry with real-world errors show that our proposal can achieve higher accuracy in cleaning dirty tuples, compared to the state-of-the-art methods.

Misplaced data in a tuple are prevalent, e.g., a value "Passport" is misplaced in the passenger-name attribute, which should belong to the travel-document attribute instead. While repairing in-attribute errors have been widely studied, i.e., to repair the error by other values in the attribute domain, misplacement errors are surprisingly untouched, where the true value is simply misplaced in some other attribute of the same tuple. For instance, the true passenger-name is indeed misplaced in the travel-document attribute of the record. In this sense, we need a novel swapping repair model (to swap the misplaced passenger-name and travel-document values "Passport" and "John Adam" in the same tuple). Determining a proper swapping repair, however, is non-trivial. The minimum change criterion, evaluating the distance between the swapping repaired values, is obviously meaningless, since they are from different attribute domains. Intuitively, one may examine whether the swapped value ("John Adam") is similar to other values in the corresponding attribute domain (passenger-name). In a holistic view of all (swapped) attributes, we propose to evaluate the likelihood of a swapping repaired tuple by studying its distances (similarity) to neighbors. The rationale of distance likelihood refers to the Poisson process of nearest neighbor appearance. The optimum repair problem is to find a swapping repair with the maximum likelihood on distances. Experiments over datasets with real-world misplaced attribute values demonstrate the effectiveness of our proposal in repairing misplacement.

Missing values may appear in various attributes. By "various", we mean (1) different types of values in a tuple, such as numerical or categorical, and (2) different attributes in a tuple, either the dependent or determinant attributes of regression models or dependency rules. Such varieties unfortunately prevent the imputation performing. In this paper, we propose to study the distance models that predict distances between tuples for missing data imputation. The immediate benefits are in two aspects, (1) uniformly processing and collaboratively utilizing the distances on all the attributes with various types of values, and (2) rather than enumerating the combinations of imputation candidates on various attributes, we can directly calculate the most likely distances of missing values to other complete ones and thus infer the corresponding imputations. Our major technical highlights include (1) introducing the imputation statistically explainable by the likelihood on distances, (2) proving NP-hardness of finding the maximum likelihood imputation, and (3) devising the approximation algorithm with performance guarantees. Experiments over datasets with real missing values demonstrate the superiority of the proposed method compared to 11 existing approaches in 5 categories. Our proposal improves not only the imputation accuracy but also the downstream applications such as classification, clustering and record matching.

Incomplete information often occurs along with many database applications, e.g., in data integration, data cleaning, or data exchange. The idea of data imputation is often to fill the missing data with the values of its neighbors who share the same/similar information. Such neighbors could either be identified certainly by editing rules or extensively by similarity relationships. Owing to data sparsity, the number of neighbors identified by editing rules w.r.t. value equality is rather limited, especially in the presence of data values with variances. To enrich the imputation candidates, a natural idea is to extensively consider the neighbors with similarity relationship. However, the candidates suggested by these (heterogenous) similarity neighbors may conflict with each other. In this paper, we propose to utilize the similarity rules with tolerance to small variations (instead of the aforesaid editing rules with strict equality constraints) to rule out the invalid candidates provided by similarity neighbors. To enrich the data imputation, i.e., imputing the missing values more, we study the problem of maximizing the missing data imputation. Our major contributions include (1) the NP-hardness analysis on solving as well as approximating the problem, (2) exact algorithms for tackling the problem, and (3) efficient approximation with performance guarantees. Experiments on real and synthetic data sets demonstrate the superiority of our proposal in filling accuracy. We also demonstrate that the record matching application is indeed improved, after applying the proposed imputation.

Missing numerical values are prevalent, e.g., owing to unreliable sensor reading, collection and transmission among heterogeneous sources. Unlike categorized data imputation over a limited domain, the numerical values suffer from two issues: (1) sparsity problem, the incomplete tuple may not have sufficient complete neighbors sharing the same/similar values for imputation, owing to the (almost) infinite domain; (2) heterogeneity problem, different tuples may not fit the same (regression) model. In this study, enlightened by the conditional dependencies that hold conditionally over certain tuples rather than the whole relation, we propose to learn a regression model individually for each complete tuple together with its neighbors. Our IIM, Imputation via Individual Models, thus no longer relies on sharing similar values among the k complete neighbors for imputation, but utilizes their regression results by the aforesaid learned individual (not necessary the same) models. Remarkably, we show that some existing methods are indeed special cases of our IIM, under the extreme settings of the number ℓ of learning neighbors considered in individual learning. In this sense, a proper number ℓ of neighbors is essential to learn the individual models (avoid over-fitting or under-fitting). We propose to adaptively learn individual models over various number ℓ of neighbors for different complete tuples. By devising efficient incremental computation, the time complexity of learning a model reduces from linear to constant. Experiments on real data demonstrate that our IIM with adaptive learning achieves higher imputation accuracy than the existing approaches.