The scale of data analysis tasks have increased, highlighting the critical importance of data quality. Data quality assessment and repair have become pivotal in data preparation. Despite the availability of numerous algorithms for data cleaning, these often focus on optimizing efficiency and minimizing labor costs, neglecting the explicit relationship between data quality management costs and benefits. This omission can lead to the failure of promising data analysis solutions. To address this, we propose CBAClean, a comprehensive system that integrates cost-benefit analysis into data cleaning. CBAClean aims to assist users in quantifying the costs of data quality management and providing optimal data cleaning solutions tailored to their needs. Key features include task-centered multi-perspective data quality assessment, a comprehensive data quality repair operator library, fine-grained human role division for effective cost control, and recommendation of optimal data cleaning solutions based on cost-benefit calculations. By incorporating cost-benefit analysis, CBAClean enhances the practical application of data quality management on real-world data governance platforms.

Denial constraints are vital in data quality management, but traditional mining algorithms struggle with time series data. To address this, we introduce a novel data quality rule, threshold Denial Constraints ($t$DCs), which enables predicate scaling in numerical contexts. We formalize the inference system for$t$DCs and demonstrate the monotonicity and abruptness of threshold predicates. To efficiently mine$t$DCs, we design the tDCDiscover algorithm, which leverages batch computation of differences and thresholds to significantly reduce the time required for acquiring homologous predicate evidence, achieving a 50% -66% decrease. Additionally, we introduce an evidence matrix to store evidence, lowering the complexity of evidence matching from$O(m)$to$O(1)$. We propose two pruning strategies: triviality pruning and prediction coverage pruning, to effectively decrease the search paths to one-fifth of their original number and eliminating at least 90% of unnecessary paths. We theoretically prove that tDCDiscover ensures minimal, valid, and complete results. Experimental results on eight real-world datasets demonstrate that, compared to the current state-of-the-art denial constraint mining techniques, tDCDiscover achieves more than double the efficiency when processing high-dimensional time series data. In downstream data cleaning tasks, tDCDiscover improves error detection precision by an average of 40% and repair accuracy by 18%, further offering advantages in time series data quality management.

In time series visualization, sampling is used to reduce the number of points while retaining the visual features of the raw time series. Area-based Largest Triangle Sampling (LTS) excels at preserving perceptually critical points. However, the heuristic solution to LTS by sequentially sampling points with the locally largest triangle area (a.k.a. Largest-Triangle-Three-Buckets, LTTB) suffers from suboptimal solution and query inefficiency. We address the shortcomings by contributing a novel Iterative Largest Triangle Sampling (ILTS) algorithm with convex hull acceleration. It refines the sampling results iteratively, capturing a broader perspective by integrating more points in each iteration. Remarkably, we prove that the largest triangle can always be found in the precomputed convex hulls, making the iterative sampling still efficient. Experiments demonstrate increased visual quality over state-of-the-art baselines and significant speedups over the brute force approach.

Missing data prevalent in information systems impacts data diversity and fidelity, which systematically degrade clustering performance through biased similarity measures and unstable cluster boundaries. Current large-scale environments lack standardized imputation-clustering pipelines, as existing methods operate independently of downstream tasks without analyzing error propagation effects, leading to unreliable results. To address this, we propose TARImpute, a Task-Aware auto-Recommender system for missing value imputation for clustering. It owns three integrated features: Imputation Impact Profiler for quantitative evaluation of imputation-clustering interactions, Error Propagation Interpreter enabling explainable modeling of imputation error diffusion, and Adaptive Strategy Optimizer for dynamic selection of optimal imputation methods. TARImpute provides state-of-the-art imputation methods to evaluate their effects on clustering tasks. TARImpute also provides robust, interpretable solutions for low-quality data and shows extensibility to other analytical tasks.

Data cleaning is an essential technique to enhance data quality. Despite the proposal of various algorithms with different cleaning strategies, current automated cleaning technologies still fall short of practical requirements when dealing with large-scale data containing mixed errors. This paper presents UniClean to efficiently solve the mixed error cleaning problem with three key technical contributions. (1) A unified construction and extension method for cleaners, enabling cleaning methods to easily utilize various cleaners to perform cleaning tasks. (2) Three optimization strategies to achieve efficiency-oriented cleaning preparation. (3) A cleaning algorithm based on an optimized cleaning process to effectively clean mixed errors. UniClean achieves a time complexity of O (| D error | 4 · | Op | + |D| · | D error |), significantly enhancing scalability. Experiments on public and large-scale enterprise datasets demonstrate that UniClean achieves over 40% improvement across five metrics, compared to five state-of-the-art cleaning methods, and delivers more than 30% gains in F1 and REDR on complex datasets, while completing the cleaning process within hours even for millions of records.

Real-world datasets often suffer from multiple quality issues, hindering downstream model performance and increasing cleaning costs. To address this, we propose DemandClean, a reinforcement learning-based adaptive data cleaning framework that dynamically balances cleaning effectiveness and operational costs. DemandClean explicitly considers data authenticity (alignment with real-world facts), diversity (richness of feature values), and downstream models' noise tolerance. We categorize data errors as missing (reducing authenticity and diversity), semantic (affecting only authenticity), and syntactic (affecting authenticity but potentially increasing diversity). Based on these errors, DemandClean intelligently selects among Repair, Delete, or No actions, guided by error rates and model robustness. For interpretability, the framework visually distinguishes authenticity, diversity, and tolerance. Extensive experiments confirm that DemandClean achieves near-optimal accuracy at substantially reduced preprocessing costs. Specifically, it reduces repair actions by 80.0% and deletions by 80.7% compared to "Repair All" strategies, while maintaining or even exceeding their predictive performance, thus offering an interpretable, cost-effective, and scalable solution for practical applications.

A typical industrial scenario encounters thousands of devices with millions of sensors, consistently generating billions of data points. It poses new requirements of time series data management, not well addressed in existing solutions, including (1) device-defined ever-evolving schema, (2) mostly periodical data collection, (3) strongly correlated series, (4) variously delayed data arrival, and (5) highly concurrent data ingestion. In this paper, we present a time series database management system, Apache IoTDB. It consists of (i) a time series native file format, TsFile, with specially designed data encoding, and (ii) an IoTDB engine for efficiently handling delayed data arrivals and processing queries. We introduce a native distributed solution with distributed queries optimized by parallel operators. We also explore efficient TsFile synchronization mechanisms, ensuring seamless data integration without the need for ETL processes. The system achieves a throughput of 10 million inserted values per second. Queries such as 1-day data selection of 0.1 million points and 3-year data aggregation over 10 million points can be processed in 100 ms. Comparisons with InfluxDB, TimescaleDB, KairosDB, Parquet and ORC over real world data loads demonstrate the superiority of IoTDB and TsFile.

Intelligent devices often produce time series data that suffer from significant data quality issues. While the utilization of data dependency in error detection and data repair has been somewhat beneficial, it remains inadequate in accurately representing the data quality of time series datasets. In recognition of the obvious characteristics inherent in time series data, we introduce a novel data dependency, termed TSDD. It effectively captures the contextual relationships embedded within multivariate time series, thereby enhancing the semantic richness of data quality representations. We analyze the complexity of both implication and consistency problems for TSDD reasoning, and develop TSDD discovery algorithm TSDDISCOVER, which consists of functional structure discovery, allowable error bound determination, and validation of TSDD patterns. Experimental results on real-life datasets verify TSDDISCOVER efficiently discovers high-quality TSDD patterns. In comparing the performance of TSDD-based error detection with several leading data quality constraints, our findings reveal that the former achieves an average improvement of 12% in accuracy and 30% in the F1 score over other dependency-based detection methods.

Time series data generated by thousands of sensors are suffering data quality problems. Traditional constraint-based techniques have greatly contributed to data cleaning applications. However, cleaning methods that support expressive constraints on time series data remain insufficient. Given the notable characteristics of time series data, existing cleaning approaches are challenged to provide good repair solutions. To address the challenges, we propose a novel data cleaning method for time series which incorporates expressive constraints that support arithmetic operations between attributes and time context. In the violation detection phase, we introduce specialized violation degree quantification functions and design a violation cell discovery algorithm to identify errors hidden in time series data. In the data repairing phase, we formalize the cleaning task as a constrained optimization problem and develop a novel repair objective function that considers both modification costs and conformance degrees of constraints. We effectively reduce the repair search space through the evaluation of time-context constraints and propose a bidirectional repairing algorithm. We also provide theoretical analysis of the proposed repairing method. Experimental results on three real-world IoT datasets across five metrics demonstrate that our proposed method outperforms seven state-of-the-art cleaning techniques specialized for time series data. Specifically, we achieve a 60% improvement in repairing effectiveness and a 70% reduction in time costs with our designed cleaning strategy.

Assessing data quality through Functional Depen-dencies (FDs) is a crucial aspect of data governance. However, with the diverse range of data sources and the exponential growth in data volume, exact FDs can sometimes be impractical for real-world applications. In contrast, relaxed functional dependencies (RFDs), which allows for some flexibility in attribute value comparisons, demonstrates greater adaptability and flexibility for big data scenarios. To address the efficient discovery of RFDs, this paper proposes a novel mining method to supplement the current research gaps. By establishing a difference table for tuples, we transform the problem into a specialized minimal set covering problem. Additionally, we introduce two optimization strategies: reducing the time complexity of enumerating the left-hand side of the base RFDs to 0 (1) and decreasing the search complexity for feasible LHS attributes and threshold candidates from O(2m-l) to O(1.5m-1). We rigorously proof that our mining approach guarantees the identification of validity and minimal RFDs. Experiments on nine real-world datasets reveal that our method significantly improves efficiency compared to existing techniques. Furthermore, it uncovers more concise and higher-quality RFDs. Importantly, the RFDs extracted through our methodology exhibit better performance in downstream cleaning tasks.

Raft has been widely adopted as the consensus protocol in various distributed systems, owing to its straight-forward interpretation and implementation. However, directly applying Raft may not fully meet the extremely high throughput requirement in the Internet of Things (IoT) scenarios. The case study on real IoT applications reveals unique features, such as high concurrency, fluctuating traffic, fixed-size requests, and compressible data. It explains the bottlenecks of the Raft leader in dispatching, persistence, and memory management, for IoT applications. To this end, we propose to explore the opportunities of tuning Raft for the particular IoT workload, including alternative data structures, various compression algorithms, memory recycling strategies, etc. This paper presents a systematic evaluation of Raft by tuning the aspects above, in an open-source time series database Apache IoTDB. The extensive experiments demonstrate improved system parallelism, reduced information redundancy, and increased resource utilization. The throughput improvement ranges from 10% by replacing the dispatching data structure to nearly 200% by pre-serialization. The overall throughput can reach 4x compared with the original Raft implementation.

Regression models are employed in lossless compression of time series data, by storing the residual of each point, known as regression encoding. Owing to value fluctuation, the regression residuals could be large and thus occupy huge space. It is worth noting that compared to the fluctuating values, time intervals are often regular and easy to compress, especially in the IoT scenarios where sensor data are collected in a preset frequency. In this sense, there is a trade-off between storing the regular timestamps and fluctuating values. Intuitively, rather than in time order, we may exchange the data points in the series such that the nearby ones have both smoother timestamps and values, leading to lower residuals. In this paper, we propose to reorder the time series data for better regression encoding. Rather than recomputing from scratch, efficient updates of residuals after moving some points are devised. The experimental comparison over various real-world datasets, either public or collected by our industrial partners, illustrates the superiority of the proposal in compression ratio. The method, REGression Encoding with Reordering (REGER), has now become an encoding method in an open-source time series database, Apache IoTDB.

Hyperparameter optimization (HPO) is known to be costly in deep learning, especially when leveraging automated approaches. Most of the existing automated HPO methods are accuracy-based, i.e., accuracy metrics are used to guide the trials of different hyperparameter configurations amongst a specific search space. However, many trials may encounter severe training problems, such as vanishing gradients and insufficient convergence, which can hardly be reflected by accuracy metrics in the early stages of the training and often result in poor performance. This leads to an inefficient optimization trajectory because the bad trials occupy considerable computation resources and reduce the probability of finding excellent hyperparameter configurations within a time limitation. In this paper, we propose Bad Trial Tackler (BTTackler), a novel HPO framework that introduces training diagnosis to identify training problems automatically and hence tackles bad trials. BTTackler diagnoses each trial by calculating a set of carefully designed quantified indicators and triggers early termination if any training problems are detected. Evaluations are performed on representative HPO tasks consisting of three classical deep neural networks (DNN) and four widely used HPO methods. To better quantify the effectiveness of an automated HPO method, we propose two new measurements based on accuracy and time consumption. Results show the advantage of BTTackler on two-fold: (1) it reduces 40.33% of time consumption to achieve the same accuracy comparable to baseline methods on average and (2) it conducts 44.5% more top-10 trials than baseline methods on average within a given time budget. We also released an open-source Python library that allows users to easily apply BTTackler to automated HPO processes with minimal code changes\footnotehttps://github.com/thuml/BTTackler.

Quantiles are fundamental statistics in various data science tasks, but costly to compute, e.g., by loading the entire data in memory for ranking. With limited memory space, prevalent in end devices or databases with heavy loads, it needs to scan the data in multiple passes. The idea is to gradually shrink the range of the queried quantile till it is small enough to fit in memory for ranking the result. Existing methods use deterministic sketches to determine the exact range of quantile, known as deterministic filter, which could be inefficient in range shrinking. In this study, we propose to shrink the ranges more aggressively, using randomized summaries such as KLL sketch. That is, with a high probability the quantile lies in a smaller range, namely probabilistic filter, determined by the randomized sketch. Specifically, we estimate the expected passes for determining the exact quantiles with probabilistic filters, and select a proper probability that can minimize the expected passes. Analyses show that our exact quantile determination method can terminate in P passes with 1-δ confidence, storing O(N 1/P logP-1/2P (1/δ)) items, close to the lower bound Ømega(N1/P) for a fixed δ. The approach has been deployed as a function in an LSM-tree based time-series database Apache IoTDB. Remarkably, the randomized sketches can be pre-computed for the immutable SSTables in LSM-tree. Moreover, multiple quantile queries could share the data passes for probabilistic filters in range estimation. Extensive experiments on real and synthetic datasets demonstrate the superiority of our proposal compared to the existing methods with deterministic filters. On average, our method takes 0.48 fewer passes and 18% of the time compared with the state-of-the-art deterministic sketch (GK sketch).

Dirty data are prevalent in time series, such as energy consumption or stock data. Existing data cleaning algorithms present shortcomings in dirty data identification and unsatisfactory cleaning decisions. To handle these drawbacks, we leverage inherent recurrent patterns in time series, analogize them as fixed combinations in textual data, and incorporate the concept of perplexity. The cleaning problem is thus transformed to minimize the perplexity of the time series under a given cleaning cost, and we design a four-phase algorithmic framework to tackle this problem. To ensure the framework's feasibility, we also conduct a brief analysis of the impact of dirty data and devise an automatic budget selection strategy. Moreover, to make it more generic, we additionally introduce advanced solutions, including an ameliorative probability calculation method grounded in the homomorphic pattern aggregation and a greedy-based heuristic algorithm for resource savings. Experiments on 12 real-world datasets demonstrate the superiority of our methods.

When analyzing time series, often interactively, the analysts frequently demand to visualize instantly large-scale data stored in databases. M4 visualization selects the first, last, bottom and top data points in each pixel column to ensure pixel-perfectness of the two-color line chart visualization. While M4 already shows its preciseness of encasing time series in different scales into a fixed size of pixels, how to efficiently support M4 representation in a time series native database is still absent. It is worth noting that, to enable fast writes, the commodity time series database systems, such as Apache IoTDB or InfluxDB, employ LSM-Tree based storage. That is, a time series is segmented and stored in a number of chunks, with possibly out-of-order arrivals, i.e., disordered on timestamps. To implement M4, a natural idea is to merge online the chunks as a whole series, with costly merge sort on timestamps, and then perform M4 representation as in relational databases. In this study, we propose a novel chunk merge free approach called M4-LSM to accelerate M4 representation and visualization. In particular, we utilize the metadata of chunks to prune and avoid the costly merging of any chunk. Moreover, intra-chunk indexing and pruning are enabled for efficiently accessing the representation points, referring to the special properties of time series. Remarkably, the time series database native operator M4-LSM has been implemented in Apache IoTDB, an open-source time series database, and deployed in companies across various industries. In the experiments over real-world datasets, the proposed M4-LSM operator demonstrates high efficiency without sacrificing preciseness.

Data dependency mining plays a crucial role in understanding data relationships. To address the increasing complexities of real-world data, Approximate Functional Dependencies (AFDs) have been introduced, building upon traditional FD. However, existing AFD approaches use static relaxation coefficients, limiting their effectiveness in capturing dependencies in noisy data. We propose a dynamic AFD variant, DAFD, which incorporates attribute error rates. We establish a bijection between DAFD and FD, develop its inference system, and introduce DAFDiscover, an algorithm for mining dependencies directly on noisy data. DAFDiscover matches the time and space complexity of SOTA AFD mining methods while offering superior performance. We theoretically prove its correctness, provide a method for calculating DAFD probabilities (DAFD- prob ), and derive a lower bound for DAFD's validity on dirty data. Experimental results on multiple public datasets demonstrate the semantic superiority of DAFD and the effectiveness of DAFDiscover compared to existing SOTA AFD mining techniques.

The widespread existence of time series data in information systems poses significant challenges to data cleaning due to its quality issues, particularly the complex interdependencies among attributes and the persistence of errors. Existing semantic constraints, such as conditional regression rules and speed constraints, though helpful, remain insufficient for this task. This paper introduces two novel online cleaning methods: MTSClean and MTSClean- soft , designed to improve cleaning efficiency and robustness. By combining row and column constraints, we significantly accelerate the cleaning process, reducing the time complexity of the exact solution MTSClean from O (( NM ) 3.5 |Σ|) to O ( NM 3.5 |Σ|). Meanwhile, MTSClean- soft achieves O ( NM 2 ) and more precise repairs through optimized search for key cells and a novel repair cost function. Comparative experiments against nine benchmark methods highlight our approach's superiority in multiple metrics, completing cleaning tasks faster and performing better than state-of-the-art methods. This demonstrates the practicality and advantage of the proposed methods in cleaning multidimensional time series data.

Billions of data points are generated by devices equipped with thousands of sensors, leading to significant data quality issues in time series data. These errors not only complicate time series data management but also compromise the accuracy and reliability of analysis based on such data. Given the noteworthy characteristics of time series data, existing cleaning methods struggle to provide adequate repairs, and tools supporting expressive constraints for time series remain scarce. To address this, we develop Clean4TSDB, a specialized data cleaning system for time series databases. This system integrates three key modules: expressive data quality constraint discovery, violation detection, and multivariate time series repairing, forming a comprehensive "profiling-detection-repair" workflow. Technically, we introduce TSDD, a data quality constraint that effectively captures contextual relationships within multivariate time series, and implement an efficient algorithm for its automated mining. Leveraging both row- and column-based constraints, we propose an effective time series cleaning algorithm. From a system standpoint, Clean4TSDB is pre-configured for seamless integration with time series databases like Apache IoTDB. Using user-provided and algorithmically-mined constraints, it effectively identifies various error patterns and offers reliable cleaning solutions. Furthermore, we establish a comprehensive library of state-of-the-art time series repair algorithms to meet the diverse needs of different management scenarios.

Log-structured merge trees (LSM-trees) are commonly employed as the storage engines for write-intensive workloads in modern time series databases including Apache IoTDB. Following append-only principle, LSM-trees can handle intensive writes and updates, but consequently suffer high space amplification (SA). To reduce SA in LSM-tree, compaction is triggered periodically to reorganize a large number of immutable files on disk to eliminate redundancy. This issue is further complicated in the Internet of Things (IoT) scenarios, where frequent out-of-order data insertions and data updates introduce duplicated keys, obsolete values and overlapping bitmaps in multi-column data, thereby exacerbating SA concerns. To mitigate SA in such contexts, this paper presents a Multi-Column Compaction (MCC) strategy in Apache IoTDB, an open-source time series database utilizing LSM-tree architecture and supporting multi-column storage. We take into consideration both the separate insertions (out-of-order data) and updates of multi-column data, and analyze the hardness of selecting proper files with the maximum space reduction in compaction. We then propose a heuristic method designed to improve the file selection, thus reducing SA. To enhance the efficiency of this approach, we further devise File Prefetcher and Compaction Cache. The proposed MCC has been implemented in Apache IoTDB. Experimental results demonstrate that our proposed MCC achieves better performance in reducing space amplification.

While outlier detection has been widely studied over streaming data, the query of outliers in time series databases was largely overlooked. Apache IoTDB, an open-source time series database, employs LSM-tree based storage to support intensive writing workloads, yet this storage structure unfortunately encumbers the outlier query performing. In the system, data points of a time series may be stored in multiple files with overlapping time ranges, owing to the far delayed data arrivals, which are simply discarded in streaming outlier detection. Given the overlapping time ranges, it is not able to detect outliers in each file and merge them as the results. In this paper, we focus on optimizing the efficiency of distance-based outlier query in Apache IoTDB, with the consideration of overlapping files for delayed data. We propose to utilize bucket statistics of the values stored in files. Upper and lower bounds on the neighbor counts of data points are derived in buckets and overlapping files for efficient pruning. Extensive experiments demonstrate the efficiency of our proposal in the LSM-tree based time series database, Apache IoTDB, compared to the existing outlier detection methods designed for data streams.

The proliferation of the Internet of Things (IoT) has led to an exponential increase in time series data, distributed and applied in various contexts, demanding a dedicated storage solution. Based on our observations and analysis of IoT production systems, we have characterized 3 requirements for time series data: (1) a close association with devices and sensors, (2) continually synchronizing between cloud-edge, and (3) requiring the ability for high ingestion and low latency access on big volume data. Despite the growing trend, current time series database systems lack a standardized file format, and existing open file formats do not adequately leverage the unique characteristics of IoT time series data. In this paper, we introduce Apache TsFile, a specialized file format tailored for IoT time series data. TsFile organizes data by devices, creating indexes based on device-related information. Our experiments demonstrate the efficiency of TsFile in achieving high data ingestion rates, minimizing latency, and optimizing data compactness.

The Raft consensus protocol naturally fits time series databases, owing to the resemblance between its continuous log and the time series data. While the serialization of appending entries reduces the state space for ease design and implementation, it blocks the subsequent requests and thus limits the parallelism and throughput of Raft. Intuitively, once an entry arrives the follower, we may notice the leader and the client to unblock the subsequent as early, rather than waiting for its appending and committing. In this way, more requests can be processed in parallel, and thus the throughput increases, essential for IoT applications often with vast sensors and fast data ingestion. Of course, with higher parallelism, the risk of persistence for in-processing entries increases. It is a worthwhile trade-off in the IoT scenario since tiny data loss during leader failure is more acceptable than shutting out most data due to a low throughput. Our Non-Blocking Raft (NB-Raft) is implemented as the consensus protocol of Apache IoTDB, a commodity time series database management system, supporting various applications in Alibaba Cloud. Extensive evaluation shows that the throughput is improved by about 30% using our NB-Raft compared to the original Raft, a considerable amount of further data saved.

While time series data are naturally ordered by timestamps for efficient storage and query processing, the data points in a time series often come out-of-order. We identify two unique features of out-of-order arrivals in Apache IoTDB, i.e., delay-only and not-too-distant. It is not surprising that data points can only be delayed but should never come "earlier" before the generation of its succeeding ones. Moreover, the system employs a separation policy to handle those points delayed for a very long period, and thus only sorts data points delayed to not-too-distant future. Motivated by such unique features, we devise a new algorithm for sorting time series data, Backward-Sort. Intuitively, the delay-only feature leads to the strategy of moving points backward in sorting. Moreover, the not-too-distant feature results in blocks of data points, such that moving points are expected to occur locally inside the blocks. To our best knowledge, this is the first sorting algorithm specially designed for out-of-order arrivals in time series. The algorithm becomes a fundamental component of sorting time series data in Apache IoTDB. The evaluation is conducted over real and synthetic datasets, using IoTDB-benchmark.

Manufacturing data analytics tasks are traditionally undertaken with Mechanism Models (MMs), which are domain-specific mathematical equations modeling the underlying physical or chemical processes of the tasks. Recently, Deep Learning (DL) has been increasingly applied to manufacturing. MMs and DL have their individual pros and cons, motivating the development of Mechanism-guided Deep Learning Models (MDLMs) that combine the two. Existing MDLMs are often tailored to specific tasks or types of MMs, and can fail to effectively 1) utilize interconnections of multiple input examples, 2) adaptively self-correct prediction errors with error bounding, and 3) ensemble multiple MMs. In this work, we propose a generic, task-agnostic MDLM framework that can embed one or more MMs in deep networks, and address the 3 aforementioned issues. We present 2 diverse use cases where we experimentally demonstrate the effectiveness and efficiency of our models.

A typical industrial scenario encounters thousands of devices with millions of sensors, consistently generating billions of data points. It poses new requirements of time series data management, not well addressed in existing solutions, including (1) device-defined ever-evolving schema, (2) mostly periodical data collection, (3) strongly correlated series, (4) variously delayed data arrival, and (5) highly concurrent data ingestion. In this paper, we present a time series database management system, Apache IoTDB. It consists of (i) a time series native file format, TsFile, with specially designed data encoding, and (ii) an IoTDB engine for efficiently handling delayed data arrivals and processing queries. The system achieves a throughput of 10 million inserted values per second. Queries such as 1-day data selection of 0.1 million points and 3-year data aggregation over 10 million points can be processed in 100 ms. Comparisons with InfluxDB, TimescaleDB, KairosDB, Parquet and ORC over real world data loads demonstrate the superiority of IoTDB and TsFile.

Columnar storage is now an industry standard design in most open-source or commercial time series database products, making them HTAP systems. The time column of a time series serves as the key for identifying the other value column, namely single-column storage scheme. When multiple time series share a similar set of timestamps, very likely in a module of multiple sensors, it is natural to group them together, i.e., one time column identifies multiple value columns in a single-group storage scheme. While multiple value columns sharing the same time column reduce the space cost of repeating timestamps, it may introduce extra space cost for recording null values. The reason is that time series may not be exactly aligned on each timestamp, owing to missing values, distinct data collection frequencies, unsynchronized clocks and so on. The columngroups storage scheme is thus to divide columns into multiple groups, within which the value columns share the same time column. Unfortunately, the problem of finding the optimal column groups for the minimum space cost is highly challenging, NP-hard according to our analysis. Thereby, we propose a heuristic algorithm for automatically grouping time series for efficient columnar storage. The column groups storage has been deployed in Apache IoTDB, an open-source time series database. The extensive performance analysis, over real-world data from our industrial partners, demonstrates that the proposed column groups achieve near optimal storage, more concise than the storage of single-column or single-group schemes. Interestingly, both the flushing and querying time costs of column groups are comparable to those of single-column or singlegroup, i.e., without incurring extra time cost.

Time series has been found with various data quality issues, e.g., owing to sensor failure or network transmission errors in the Internet of Things (IoT). It is highly demanded to have an overview of the data quality issues on the millions of time series stored in a database. In this demo, we design and implement TsQuality, a system for measuring the data quality in Apache IoTDB. Four time series data quality measures, completeness, consistency, timeliness, and validity, are implemented as functions in Apache IoTDB or operators in Apache Spark. These data quality measures are also interpreted by navigating dirty points in different granularity. It is also well-integrated with the big data eco-system, connecting to Apache Zeppelin for SQL query, and Apache Superset for an overview of data quality.

LSM-Tree is widely adopted for storing time-series data in Internet of Things. According to conventional policy (denoted by$\pi_{c}$), when writing, the data will first be buffered in MemTable in memory. When it is full, the data will be written to the disk to form SSTables. Compaction is triggered to sort the data in each layer of the LSM-Tree on the disk. However, the arrival of data can be unordered due to reasons such as transition delay. Apache IoTDB uses in-order and out-of-order MemTables to separately buffer the in-order and out-of-order data to accelerate queries, namely the separation policy (denoted by$\pi_{s}$). However, given a specific space of memory budget to buffer the data, write amplification (WA) of the leveled LSM-Tree will be influenced by$\pi_{s}$. Whether the influence by separation is positive or negative, and how intense WA is influenced, depend on the properties of workloads and the capacity of the in-order and out-of-order MemTables. It is highly demanded to build robust models for estimating the expected amount of data rewritten in each compaction, and predicting the WA under$\pi_{c}$and$\pi_{s}$. Note that as an industrial paper, rather than proposing novel techniques for research problems, we focus on the practice of whether separating or not for lower write amplification. Experiments on synthetic and real-world datasets show that the models for estimating WA are accurate under various delay distributions. In addition, based on the estimation models, we implement an analyzer module in the open-source Apache IoTDB, for choosing the policy with lower WA. We apply the method in the use case of our industrial partner, a service provider of engineering machinery. The use case verifies the effectiveness of deciding whether separation or not by WA estimation.

Analyzing and mining of time series have been widely studied in both academia and industry in recent years. Given a set of long time series, data analysts can utilize the window-based similarity search to explore subsequences in arbitrary time windows. Existing techniques are not efficient for window-based query processing. In particular, the whole matching index approach needs to build an individual index for each window, which incurs huge space cost. The existing window-based approach can only cluster neighboring windows, which leads to loose bounds of each group, and thus degrades the query processing efficiency. In this paper, we propose a compact time series index (WinIdx) for efficient window query processing. Specifically, i) we propose a novel distance measurement to capture the similarity between windows, ii) WinIdx provides a compact index structure for windows within a cluster by exploiting the similarity among subsequences relationships, and iii) several optimizations (e.g., sortable summarization, summarization envelop) are equipped in WinIdx to improve the efficiency of index construction, query processing and index footprints. We conduct extensive experiments on both real and synthetic time series to demonstrate the superiority of WinIdx against state-of-the-art approaches.

Nowadays, many applications, like Internet of Things and Industrial Internet, collect data points from sensors continuously to form long time series. Finding correlation between time series is a fundamental task for many time series mining problems. However, most existing works in this area are either limited in the type of detected relations, like only the linear correlations, or not handling the complex temporal relations, like not considering the unaligned windows or variable window lengths. In this paper, we propose an efficient approach, Non-Linear Correlation search (NLC), to search the correlated window pairs on two long time series. Firstly, we propose two strategies, window shrinking and window extending, to quickly find the high-quality candidates of correlated window pairs. Then, we refine the candidates by a nested one-dimensional search approach. We conduct a systematic empirical study to verify the efficiency and effectiveness of our approach over both synthetic and real-world datasets.

In recent years, the widespread use of sensors has substantially stimulated researchers' interest in time series data mining. Real-world time series often include natural structures. For example, a time series captured from a patient rehabilitation app can be divided into a series of movements, e.g., sitting, standing, and walking. Finding time series natural structures (i.e., latent semantic states) is one of the core subroutines in time series mining applications. However, this task is not trivial as it has two challenges: (1) how to determine the correct change points between consecutive segments, and (2) how to cluster segments into different states.In this paper, we propose a novel graph-based approach, GRAB, to discover time series natural structures. In particular, GRAB first partitions the time series into a set of non-overlapping fragments via the similarity between subsequences. Then, it constructs a fragment-based graph and employs a graph partition method to cluster the fragments into states. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our GRAB method. Specifically, GRAB finds high-quality latent states, and it outperforms state-of-the-art solutions by orders of magnitude.

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.

The amount of time-series data that is generated has exploded due to the growing popularity of Internet of Things (IoT) devices and applications. These applications require efficient management of the time-series data on both the edge and cloud side that support high throughput ingestion, low latency query and advanced time series analysis. In this demonstration, we present Apache IoTDB managing time-series data to enable new classes of IoT applications. IoTDB has both edge and cloud versions, provides an optimized columnar file format for efficient time-series data storage, and time-series database with high ingestion rate, low latency queries and data analysis support. It is specially optimized for time-series oriented operations like aggregations query, down-sampling and sub-sequence similarity search. An edge-to-cloud time-series data management application is chosen to demonstrate how IoTDB handles time-series data in real-time and supports advanced analytics by integrating with Hadoop and Spark. An end-to-end IoT data management solution is shown by integrating IoTDB with PLC4x, Calcite, and Grafana.

The volume of time series data has exploded due to the popularity of new applications, such as data center management and IoT. Subsequence matching is a fundamental task in mining time series data. All index-based approaches only consider raw subsequence matching (RSM) and do not support subsequence normalization. UCR Suite can deal with normalized subsequence matching problem (NSM), but it needs to scan full time series. In this paper, we propose a novel problem, named constrained normalized subsequence matching problem (cNSM), which adds some constraints to NSM problem. The cNSM problem provides a knob to flexibly control the degree of offset shifting and amplitude scaling, which enables users to build the index to process the query. We propose a new index structure, KV-index, and the matching algorithm, KV-match. With a single index, our approach can support both RSM and cNSM problems under either ED or DTW distance. KV-index is a key-value structure, which can be easily implemented on local files or HBase tables. To support the query of arbitrary lengths, we extend KV-match to KV-match_DP, which utilizes multiple varied-length indexes to process the query. We conduct extensive experiments on synthetic and real-world datasets. The results verify the effectiveness and efficiency of our approach.

Aggregation operation plays an important role in time series database management. As the amount of data increases, current solutions such as summary table and MapReduce-based methods struggle to respond to such queries with low latency. Other approaches such as segment tree based methods have a poor insertion performance when the data size exceeds the available memory. This paper proposes a new segment tree based index called PISA, which has fast insertion performance and low latency for aggregation queries. PISA uses a forest to overcome the performance disadvantages of insertions in traditional segment trees. By defining two kinds of tags, namely code number and serial number, we propose an algorithm to accelerate queries by avoiding reading unnecessary data on disk. The index is stored on disk and only takes a few hundred bytes of memory for billions of data points. PISA can be easily implemented on both traditional databases and NoSQL systems, examples including MySQL and Cassandra. It handles aggregation queries within milliseconds on a commodity server for a time range that may contain tens of billions of data points.

Document stores that provide the efficiency of a schema-less interface are widely used by developers in mobile and cloud applications. However, the simplicity developers achieved controversially leads to complexity for data management due to lack of a schema. In this paper, we present a schema management framework for document stores. This framework discovers and persists schemas of JSON records in a repository, and also supports queries and schema summarization. The major technical challenge comes from varied structures of records caused by the schema-less data model and schema evolution. In the discovery phase, we apply a canonical form based method and propose an algorithm based on equivalent sub-trees to group equivalent schemas efficiently. Together with the algorithm, we propose a new data structure, eSiBu-Tree, to store schemas and support queries. In order to present a single summarized representation for heterogenous schemas in records, we introduce the concept of "skeleton", and propose to use it as a relaxed form of the schema, which captures a small set of core attributes. Finally, extensive experiments based on real data sets demonstrate the efficiency of our proposed schema discovery algorithms, and practical use cases in real-world data exploration and integration scenarios are presented to illustrate the effectiveness of using skeletons in these applications.

MapReduce based data-intensive computing solutions are increasingly deployed as production systems. Unlike Internet companies who invent and adopt the technology from the very beginning, traditional enterprises demand easy-to-use software due to the limited capabilities of administrators. Automatic job optimization software for MapReduce is a promising technique to satisfy such requirements. In this paper, we introduce a toolkit from IBM, called MRTuner , to enable holistic optimization for MapReduce jobs. In particular, we propose a novel Producer-Transporter-Consumer (PTC) model, which characterizes the tradeoffs in the parallel execution among tasks. We also carefully investigate the complicated relations among about twenty parameters, which have significant impact on the job performance. We design an efficient search algorithm to find the optimal execution plan. Finally, we conduct a thorough experimental evaluation on two different types of clusters using the HiBench suite which covers various Hadoop workloads from GB to TB size levels. The results show that the search latency of MRTuner is a few orders of magnitude faster than that of the state-of-the-art cost-based optimizer, and the effectiveness of the optimized execution plan is also significantly improved.

As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about “matching cross” which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms.