Data collection is a crucial task of IoTs. According to the data collection scheme and the required data granularity, data collection in IoTs can be classified into pull-based/push-based data collection as well as node-level/target-level data collection. Thus, there are four scenarios for data collection: Push-based node-level data collection (Push-Node), Push-based target-level data collection (Push-Target), Pull-based node-level data collection (Pull-Node), and Pull-based target-level data collection (Pull-Target). Energy-Harvesting IoT (EH-IoT) is an important component of IoTs and the Age of Information (AoI) minimization problem has been studied extensively for data collection in EH-IoTs. However, existing works only studied the problem under the scenario of Push-Node, Push-Target and Pull-Node. Therefore, this paper investigates the AoI minimization problem for Pull-based Target-level data collection in EH-IoTs (AoI-Pull-Target) for the first time. AoI-Pull-Target is formally defined and proved to be NP-hard. A two-stage dynamic programming-based node scheduling algorithm and a real-time schedule adjustment scheme are proposed to solve the problem. The proposed algorithm is analyzed theoretically. Extensive simulations and real-world testbed experiments verify the high performance of our algorithm.

Modern data-intensive applications require databases that support fast analytical processing on massive dynamic graphs in real time, while simultaneously providing transactional guarantees for modifying graph-based objects ( i.e. , edges, vertices and their properties). Achieving efficient Hybrid Graph Transactional/Analytical Processing (HGTAP) in a database poses significant challenges due to the simultaneous requirements of high operation throughput, high data freshness, and high performance isolation when processing concurrent read/write queries on intricate graph topology. Existing disk-based graph databases fail to meet these requirements at the same time due to their inclined data layout, such as the transactional storage based on adjacency list and the analytical storage based on CSR (compressed sparse row) format. To address these challenges, we present BACH (Bridging Adjacency List and CSR Format using LSM (Log-Structured Merge)-Trees for HGTAP Workloads) to fill the gaps in HGTAP databases. BACH expands the design space of traditional LSM-Trees to accommodate different graph data layouts in different levels. The compaction process is further extended to seamlessly transform the graph layout from the TP-friendly adjacency list to the AP-friendly CSR format through the data propagation to deeper levels in the LSM-Tree. A novel compaction policy, namely elastic merge , is carefully devised to adapt to diverse workloads and the skew vertex degree distribution on graph data. These techniques lead to a Graph-aware Real-time (GR)-LSM-Tree , which can provide consistently efficient data access for diverse workloads throughout the entire lifespan of graph objects. Then, a lightweight multi-version scheme is devised for the GR-LSM-Tree to accelerate the concurrent read/write processing with the snap-shot isolation guarantee. Comprehensive experiments demonstrate that BACH significantly outperforms other disk-based graph database solutions in HGTAP workloads.

Motif discovery is a critical operation for analyzing series data in many applications. Recent works demonstrate the importance of finding motifs with Dynamic Time Warping. However, existing algorithms spend most of their time in computing lower bounds of Dynamic Time Warping to filter out the unpromising candidates. Specifically, the time complexity for computing these lower bounds is$O(L)$for each pair of subsequences, where$L$is the length of the motif (subsequences). This paper proposes two new lower bounds, called$LB_{f}$and$LB_{M}$, both of them only cost amortized$O(1)$time for each pair of subsequences. On real datasets, the proposed lower bounds are at least one magnitude faster than the state-of-the-art lower bounds used in motif discovery while still keeping satisfying effectiveness. Based on these faster lower bounds, this paper designs an efficient motif discovery algorithm that significantly reduces the cost of lower bounds. The experiments conducted on real datasets show the proposed algorithm is 5.6 times faster than the state-of-the-art algorithms on average.

Given a dataset with incomplete data (e.g., missing values), training a machine learning model over the incomplete data requires two steps. First, it requires a data-effective step that cleans the data in order to improve the data quality (and the model quality on the cleaned data). Second, it requires a data-efficient step that selects a core subset of the data (called coreset) such that the trained models on the entire data and the coreset have similar model quality, in order to save the computational cost of training. The first-data-effective-then-data-efficient methods are too costly, because they are expensive to clean the whole data; while the first-data-efficient-then-data-effective methods have low model quality, because they cannot select high-quality coreset for incomplete data. In this article, we investigate the problem of coreset selection over incomplete data for data-effective and data-efficient machine learning. The essential challenge is how to model the incomplete data for selecting high-quality coreset. To this end, we propose the GoodCore framework towards selecting a good coreset over incomplete data with low cost. To model the unknown complete data, we utilize the combinations of possible repairs as possible worlds of the incomplete data. Based on possible worlds, GoodCore selects an expected optimal coreset through gradient approximation without training ML models. We formally define the expected optimal coreset selection problem, prove its NP-hardness, and propose a greedy algorithm with an approximation ratio. To make GoodCore more efficient, we propose optimization methods that incorporate human-in-the-loop imputation or automatic imputation method into our framework. Moreover, a group-based strategy is utilized to further accelerate the coreset selection with incomplete data given large datasets. Experimental results show the effectiveness and efficiency of our framework with low cost.

With the rapid growth of uncertain data, query processing on uncertain data has become an important research area. Although considerable efforts have been devoted to answering certain types of queries on uncertain data, how to perform restricted skyline (rskyline) queries on uncertain data remains an open problem. To fill the gap, this paper studies the all rskyline probabilities (ARSP) problem, which aims to compute the probability of each uncertain tuple appearing in the rskyline, and the most-likely rskyline (MLRS) problem, which aims to identify a set of uncertain tuples with the highest probability of being the rskyline. We prove that no algorithm can solve the ARSP problem in strongly subquadratic time, unless the orthogonal vectors conjecture fails and the MLRS problem is NP-hard. When $$\mathcal {F}$$ is a set of linear scoring functions subject to a set of linear constraints on weights, we propose two efficient algorithms for solving the ARSP problem. For a special linear constraint, we further develop an algorithm with sublinear query time. For the MLRS problem, we first design a series of data reduction rules to reduce the input data size. Then, we propose two exact algorithms with different search strategies, as well as a local search based approximation algorithm to further improve the time efficiency. Experimental results show that these two problems provide complementary and comprehensive perspectives on rskylines of uncertain datasets, and demonstrate the effectiveness and efficiency of the proposed algorithms.

Restricted skyline (rskyline) query is widely used in multi-criteria decision making. It generalizes the skyline query by additionally considering a set of personalized scoring functions$\mathcal{F}$. Since uncertainty is inherent in datasets for multi-criteria decision making, we study rskyline queries on uncertain datasets from both complexity and algorithm perspective. We formalize the problem of computing rskyline probabilities of all data items and show that no algorithm can solve this problem in truly subquadratic-time, unless the orthogonal vectors conjecture fails. Considering that linear scoring functions are widely used in practical applications, we propose two efficient algorithms for the case where$\mathcal{F}$is a set of linear scoring functions whose weights are described by linear constraints, one with near-optimal time complexity and the other with better expected time complexity. For special linear constraints involving a series of weight ratios, we further devise an algorithm with sublinear query time and polynomial preprocessing time. Extensive experiments demonstrate the effectiveness, efficiency, scalability, and usefulness of our proposed algorithms.

The Maximum Minimal Cut Problem (MMCP), a NP-hard combinatorial optimization (CO) problem, has not received much attention due to the demanding and challenging bi-connectivity constraint. Moreover, as a CO problem, it is also a daunting task for machine learning, especially without labeled instances. To deal with these problems, this work proposes an unsupervised learning framework combined with heuristics for MMCP that can provide valid and high-quality solutions. As far as we know, this is the first work that explores machine learning and heuristics to solve MMCP. The unsupervised solver is inspired by a relaxation-plus-rounding approach, the relaxed solution is parameterized by graph neural networks, and the cost and penalty of MMCP are explicitly written out, which can train the model end-to-end. A crucial observation is that each solution corresponds to at least one spanning tree. Based on this finding, a heuristic solver that implements tree transformations by adding vertices is utilized to repair and improve the solution quality of the unsupervised solver. Alternatively, the graph is simplified while guaranteeing solution consistency, which reduces the running time. We conduct extensive experiments to evaluate our framework and give a specific application. The results demonstrate the superiority of our method against two techniques designed.

Given a dataset with incomplete data (e.g., missing values), training a machine learning model over the incomplete data requires two steps. First, it requires a data-effective step that cleans the data in order to improve the data quality (and the model quality on the cleaned data). Second, it requires a data-efficient step that selects a core subset of the data (called coreset) such that the trained models on the entire data and the coreset have similar model quality, in order to improve the training efficiency. The first-data-effective-then-data-efficient methods are too costly, because they are expensive to clean the whole data; while the first-data-efficient-then-data-effective methods have low model quality, because they cannot select high-quality coreset for incomplete data. In this paper, we investigate the problem of coreset selection over incomplete data for data-effective and data-efficient machine learning. The essential challenge is how to model the incomplete data for selecting high-quality coreset. To this end, we propose the GoodCore framework towards selecting a good coreset over incomplete data with low cost. To model the unknown complete data, we utilize the combinations of possible repairs as possible worlds of the incomplete data. Based on possible worlds, GoodCore selects an expected optimal coreset through gradient approximation without training ML models. We formally define the expected optimal coreset selection problem, prove its NP-hardness, and propose a greedy algorithm with an approximation ratio. To make GoodCore more efficient, we further propose optimization methods that incorporate human-in-the-loop imputation or automatic imputation method into our framework. Experimental results show the effectiveness and efficiency of our framework with low cost.

Computing a maximum independent set (MaxIS) is a fundamental NP-hard problem in graph theory, which has important applications in a wide spectrum of fields. Since graphs in many applications are changing frequently over time, the problem of maintaining a MaxIS over dynamic graphs has attracted increasing attention over the past few years. Due to the intractability of maintaining an exact MaxIS, this paper aims to develop efficient algorithms that can maintain an approximate MaxIS with an accuracy guarantee theoretically. In particular, we propose a framework that maintains a$(\displaystyle \frac{\triangle}{2}+1)$-approximate MaxIS over dynamic graphs and prove that it achieves a constant approximation ratio in many real-world networks. To the best of our knowledge, this is the first non-trivial approximability result for the dynamic MaxIS problem. Following the framework, we implement an efficient linear-time dynamic algorithm and a more effective dynamic algorithm with near-linear expected time complexity. Our thorough experiments over real and synthetic graphs demonstrate the effectiveness and efficiency of the pro-posed algorithms, especially when the graph is highly dynamic.

Massive, heterogeneous sensors have been deployed to monitor many objects from multiple aspects, which brings the explosion of sensor data; thus, effective data collection becomes an important issue. Moreover, in emerging advanced IoT applications such as the smart city, computation tasks are released by smartphone users. Such tasks are random and unpredictable, which makes it hard to know in advance what sensor data are needed. Collecting all of the data that might be involved can lead to a huge waste of time, energy, and channel resources. In this article, we study effective sensor data collection problem and the goal is to fetch enough data to get the accurate results of random tasks with minimum cost. We propose a novel progressive computing method, where the sensor data are collected in phases. Specifically, in each collection phase, the server analyzes the data obtained in preview phases and determines what data to fetch in the next phase. Then, the server sends control messages to corresponding sensors by using the downlink communication of Lora. In our computing method, data collection is interwoven with task computing, which enables targeted approaches to the data exactly needed. Two example progressive algorithms are presented, and their performances are analyzed theoretically. Simulation results show that our algorithms can reduce the cost remarkably without loss in the accuracy of the computation results.

Resilience problem is defined on a database d, given a boolean query q where q(d) is initially true, and an integer k, it is to find the tuple set d′ of smallest size such that the query result q(d∖d′) becomes false. As a potential explanation of a specified query, resilience plays a fundamental and important role in query explanation, database debugging and error tracing. Complexity results of resilience decision on relational algebraic queries have been studied previously. In this paper, we investigate the resilience decision problem on aggregation queries. New results on the hardness are provided. We show that, this problem is polynomially intractable on nested COUNT and SUM query both under data complexity and parametric complexity, and even it is NP-hard to approximate it within a constant ratio under the active domain constraint.

This paper studies the deletion propagation problem in terms of minimizing view side-effect. It is a problem funda-mental to data lineage and quality management which could be a key step in analyzing view propagation and repairing data. The investigated problem is a variant of the standard deletion propagation problem, where given a source database D, a set of key preserving conjunctive queries Q, and the set of views V obtained by the queries in Q, we try to identify a set T of tuples from D whose elimination prevents all the tuples in a given set of deletions on views △V while preserving any other results. The complexity of this problem has been well studied for the case with only a single query. Dichotomies, even trichotomies, for different settings are developed. However, no results on multiple queries are given which is a more realistic case. We study the complexity and approximations of optimizing the side-effect on the views, i.e., find T to minimize the additional damage on V after removing all the tuples of △V. We focus on the class of key-preserving conjunctive queries which is a dichotomy for the single query case. It is surprising to find that except the single query case, this problem is NP-hard to approximate within any constant even for a non-trivial set of multiple project-free conjunctive queries in terms of view side-effect. The proposed algorithm shows that it can be approximated within a bound depending on the number of tuples of both V and △V. We identify a class of polynomial tractable inputs, and provide a dynamic programming algorithm to solve the problem. Besides data lineage, study on this problem could also provide important foundations for the computational issues in data repairing. Furthermore, we introduce some related applications of this problem, especially for query feedback based data cleaning.

Recent trends show that the popularity of online social networks (OSNs) has been increasing rapidly. From daily communication sites to online communities, an average person's daily life has become dependent on these online networks. Hence, it has become evident that protection should be provided to these networks from unwanted intruders. In this paper, we consider data privacy on online social networks at the network level rather than user level. This network level privacy helps us to prevent information leakage to third-party users like advertisers. We propose a novel scheme that combines both node and edge privacy of the OSN by clustering the similar users. We further improve traditional clustering by utilizing the concept of k-anonymity. Our enhanced equicardinal clustering ensures that there are at least k users in any given network. We further provide proofs on how the proposed equicardinal clustering ensures k-anonymity and the maximum information loss. With the help of two real-world data sets, we evaluate this method in terms of privacy and efficiency.

The view propagation problem is a class of view update problem in relational databases [7], involving deletion and insertion propagations. Given source database D, conjunctive query Q, view V generated by query Q(D) and a deletion (insertion) on view ΔV, deletion (insertion) propagation is to find a side effect free update ΔD on D such that the deletion (insertion) of ΔD from (into) D will delete (insert) the intentional ones ΔV without resulting in the deletion (insertion) of additional tuples from (into) the view. Generally, such a deletion (insertion) is side effect free. The related data management applications include query result explanation, data debugging, and anonymizing datasets, which rely on understanding how interventions in a database affect the output of a query. View propagation is a natural and typical way to define such interventions, which seems to be well-studied. However, in general, the candidate update on a source database is picked up aimlessly in advance, making the updated database to be very distant from the original one no matter whether it is the maximum one. In this paper, we formally define the bounded view propagation problem, where candidate update ΔD is bounded as a subset of potential C which is a fixed small tuple set of D. We study the complexity of this problem for conjunctive queries, and make contributions to the previous results of the problems of side-effect free deletion propagation. Specifically, our bounded view propagation problem decreases computational complexity regardless of conjunctive query structure. We show the fixed potential is actually a dichotomy for both deletion and insertion propagations, and figure out the results on combined complexity which is neglected previously. Based on our results, for view propagation, we map out a complete picture of the computational complexity hierarchy for conjunctive queries on both data and combined complexities. Moreover, this bounded version is an update forbidden case of view propagation, and our results can be applied to it.