The Cloud-Edge-Device (CED) architecture has emerged as a new framework for real-time data processing in the Internet of Things (IoT) era. However, the edge and device face significant resource constraints that prevent them from storing or processing full datasets. Effective data partition across CED architectures is therefore critical for supporting real-time decision-making. However, existing static and coarse-grained dynamic methods fail to adapt to changing workloads and to meet real-time processing demands. To address this issue, we propose${\sf FinePar}$, a fine-grained dynamic data partitioning framework based on DRL, coupled with an efficient data allocation strategy.${\sf FinePar}$combines horizontal and vertical partition to optimize data partition across CED architectures to reduce data transfer volume and shorten execution time. We use DRL to adjust data partitioning strategies in real time based on task demands and resource states. To achieve end-to-end optimization, we design an efficient data allocation strategy. We verified the effectiveness of${\sf FinePar}$through extensive experiments. Experimental results show that${\sf FinePar}$can reduce the edge side latency by 80% under resource constraints and dynamically adapts to workload changes.

How should we perform anomaly detection on multivariate time-series data with missing data, attribute misplacement and concept drift? The majority of existing anomaly detection methods overlook the fact that data are often of low quality. To address this challenge, we propose an adaptive unsupervised anomaly detection method for low-quality multivariate time series data. Our method introduces a self-attention mechanism that integrates masked information and missing length information to enhance the model's capability in handling incomplete data. Furthermore, we design a deep probabilistic adaptive memory network to improve the model's adaptability to attribute misplacement and concept drift. We also discuss the optimal window size for effectively dealing with concept drift. Comparative experiments on multiple real-world datasets demonstrate that our method can effectively detect anomalies in low-quality multivariate time series data. The experimental results further highlight the robustness of our model, proving its ability to maintain high performance in the presence of data quality issues.

Trajectory similarity search is a basic operation in spatial data analysis for nonterrestrial networks applications, such as asset tracking, maritime transportation, and urban air mobility. In many real-world applications (e.g., Flickr, Bikely, and Foursquare), users are allowed to share comments or experiences along with their trajectories, called semantic trajectories. In this article, we study a new type of similarity search on semantic trajectories, which takes into account spatial and textual information together. Given a query trajectory$t_{q}$and a similarity threshold$\theta $, semantic trajectory similarity search retrieves all trajectories whose spatial-textual similarity to$t_{q}$is no greater than$\theta $. To address the problem efficiently, we first develop a novel bitmap-based index, called SET-tree, to organize the semantic trajectory hierarchically. It contains two types of bitmaps, global gram bitmap and positional gram bitmap, that enable us to efficiently prune the search space by spatial and textual similarity simultaneously. Besides, we develop some novel upper and lower bounds on textual and spatial similarity for pruning. We provide the spatial-side enhancement and the textual-side enhancement for further improvement. Finally, we report on extensive experiments using real and synthetic trajectory data sets that offer insight into the performance of our algorithm, and show that our algorithm is capable of achieving superior efficiency and good scalability.

Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. This query returns an optimal site from a candidate set to maximize itsinfluence. Existing work commonly focuses on outdoor spaces. In practice, however, people spend up to 87% of their daily life inside indoor spaces. The outdoor techniques fall short in indoor spaces due to the complicated topology of indoor spaces. In this paper, we formulate two indoor Max-Inf queries:Top-$k$kProbabilistic Influence Query (T$k$kPI)andCollective-$k$kProbabilistic Influence Query (C$k$kPI)taking probability and mobility factors into consideration. We propose a novel spatial index, IT-tree, which utilizes the properties of indoor venues to facilitate the indoor distance computation, and then applies a trie to further organize the trajectories with similar check-in partitions together, based on their sketch information. This structure is simple but highly effective in pruning the trajectory search space. To process T$k$PI efficiently, we devise subtree pruning and progressive pruning techniques to delicately filter out unnecessary trajectories based on probability bounds and the monotonicity of influence probability. For C$k$PI queries, which is a submodular NP-hard problem, three approximation algorithms are provided with different strategies of computing marginal influence value during the search. Through extensive experiments on several real indoor venues, we demonstrate the efficiency and effectiveness of our proposed algorithms.

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.

Learned cardinality estimation methods have achieved high precision compared to traditional methods. Among learned methods, query-driven approaches have faced the work-load drift problem for a long time. Although both data-driven and hybrid methods are proposed to avoid this problem, most of them suffer from high training and estimation costs, limited scalability, instability, and long-tail distribution problems on high-dimensional tables, which seriously affects the practical application of learned cardinality estimators. In this paper, we prove that most of these problems are directly caused by the widely used progressive sampling. We solve this problem by introducing predicate information into the autoregressive model and propose Duet, a stable, efficient, and scalable hybrid method to estimate cardinality directly without sampling or any non-differentiable process, which can not only reduce the inference complexity from$O(n)$to$O(1)$compared to Naru and UAE but also achieve higher accuracy on high cardinality and high-dimensional tables. Experimental results show that Duet can achieve all the design goals above and be much more practical. Besides, Duet even has a lower inference cost on CPU than that of most learned methods on GPU.

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.

In a wide variety of applications, such as indoor position selection for advertising and setting rents of different shops in a shopping mall, it is better to get the passenger flow of each room. In the indoor space, the positions of users are commonly captured by the indoor positioning system consisting of static positioning devices. And the sequence of all tracking events with the same user ordered by the corresponding time is the indoor trajectory of this user. Thus, in this paper, we define and study two essential queries named Rooms with top- k passenger flows at a Timestamp query (R k T for short) and Rooms with top- k passenger flows within a time Interval query (R k I for short), i.e., how to search rooms with top- k passenger flows at a timestamp and within a time interval in the past using indoor trajectories, respectively. For the indoor positioning system, there are only limited static positioning devices deployed in the indoor space on account of the cost. And the detection ranges of these static positioning devices only cover a small part of the indoor space. When a user is in the undetected state, there is uncertainty in its position combined with the quite complex indoor topology. Such uncertainty brings great challenges to determining the passenger flow in each room. Considering the distribution of static positioning devices, we propose a new method about how to reasonably infer where a user is in the undetected state and the corresponding probability based on its indoor trajectory and the complex indoor topology. In order to quickly retrieve the set of indoor trajectories, we propose a full Binary tree indexing indoor trajectories divided by Time intervals (BiT for short), which is built on the given set of indoor trajectories. Based on the index BiT, we propose PAT Algorithm and PAI Algorithm to efficiently process R k T and R k I queries, respectively. Extensive experiment results demonstrate superior performance of PAT Algorithm and PAI Algorithm.

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.

This paper explores the routing problem in ambient backscatter wireless sensor networks (AB-WSNs) using reinforcement learning approaches. Ambient RF signals serve as the only power source for battery-less sensor nodes and are also leveraged to enable backscatter communication among these nodes. This results in intermittent connection and dynamic topology within AB-WSNs, thereby making it difficult to route data to the sink, e.g., data may not reach the sink in a timely manner. We first introduce a multi-agent network model with two mechanisms to address this issue. We then model the routing problem with the Markov decision process, allowing each node to make informed route decisions based on the current state of its neighbors. With the aim of enabling each node to learn the optimal routing policy and do adaptive stateless routing, we propose two learning algorithms. The first, a value-based learning algorithm, is designed for sparse AB-WSNs. And the second, a policy-based learning algorithm, is intended to tackle the curse of dimensionality in dense AB-WSNs. We analyze the convergence of both learning algorithms and evaluate their performance through extensive experiments. The experiment results validate the convergence and efficiency of the proposed learning algorithms under various conditions.

In recent years, the problem of traffic congestion has become a hot topic. Accurate traffic flow prediction methods have received extensive attention from many researchers all over the world. Although many methods proposed at present have achieved good results in the field of traffic flow prediction, most of them only consider the static characteristic of traffic data, but do not consider the dynamic characteristic of traffic data. The factors that affect traffic flow prediction are changeable, and they will change over time. In response to this dynamic characteristic, the authors propose a model fusion mechanism based on transformer (TransFusion). The authors adopt two basic forecasting models (TCN and LSTM) as the underlying architectures. In view of the performance of different models on the traffic data at different times, the authors design a model fusion mechanism to assign dynamic weights to basic models at different times. Experiments on three datasets have proved that TransFusion has a significant improvement compared with basic models.

Abstract Anomaly detection is one of the most important research contents in time series data analysis, which is widely used in many fields. In real world, the environment is usually dynamically changing, and the distribution of data changes over time, namely concept drift. The accuracy of static anomaly detection methods is bound to be reduced by concept drift. In addition, there is a sudden concept drift, which is manifested as a abrupt variation in a data point that changes the statistical properties of data. Such a point is called a change point, and it has very similar behavior to an anomaly. However, the existing methods cannot distinguish between anomaly and change point, so the existence of change point will affect the result of anomaly detection. In this paper, we propose an unsupervised method to simultaneously detect anomaly and change point for time series with concept drift. The method is based on the fluctuation features of data and converts the original data into the rate of change of data. It not only solves the concept drift, but also effectively detects and distinguishes anomalies and change points. Experiments on both public and synthetic datasets show that compared with the state-of-the-art anomaly detection methods, our method is superior to most of the existing works and significantly superior to existing methods for change point detection. It fully demonstrates the superiority of our method in detecting anomalies and change points simultaneously.

Social Internet of Things (SIoT) incorporates social relationship into the Internet of Things (IoT), and a compositive relationship between persons, devices, and persons to devices is utilized for providing better services. This article proposes a novel type of search, namely, top-$k$social spatial keyword search (SSKS) in SIoT networks to discover relevant users or data objects according to social, spatial, and textual preferences. Existing works mainly focus on two of these preferences at the same time, and efficiently processing top-$k$SSKS remains challenging. To this end, we propose two algorithms to evaluate top-$k$SSKS in SIoT networks. The first algorithm is a forward search-based algorithm, which spreads the search from the vertex of the querying user. An effective pruning strategy is established by recognizing an early termination condition according to the threefold preference. The forward search-based algorithm is efficient when textual objects are dense. The second algorithm is based on index searching. We present an index namely 2HL-GIL to support spatial and textual pruning while providing fast computation of social distances in the SIoT. Then an index-based search algorithm is proposed for top-$k$SSKS, and it is efficient especially when textual objects are sparse. Our proposed algorithms are evaluated over two real-life social networks attached with synthetic locations and textual data. Evaluation results illustrate the effectiveness and efficiency of our proposed forward search-based algorithm and index-based search algorithm.

Modern applications and services leveraged by interactive cyberphysical systems (CPS) are providing significant convenience to our daily life in various aspects at present. Clients submit their requests including query contents to CPS servers to enjoy diverse services such as health care, automatic driving, and location-based services. However, privacy concerns arise at the same time. Content privacy is recognized and a lot of efforts have been made in the literature of privacy preserving in interactive cyberphysical systems such as location-based services. Nevertheless, neither the cloaking based solutions nor existing client based solutions have achieved effective content privacy by optimizing proper content privacy metrics. In this paper we formulate the problem of achieving the optimal content privacy in interactive cyberphysical systems using k -anonymity solutions based on two content privacy metrics, which are defined using the concepts of entropy and differential privacy. Then we propose an algorithm, Multilayer Alignment (MLA), to establish k -anonymity mechanisms for preserving content privacy in interactive cyberphysical systems. Our proposed MLA is theoretically proved to achieve the optimal content privacy in terms of both the entropy based and the differential privacy mannered content privacy metrics. Evaluation based on real-life datasets is conducted, and the evaluation results validate the effectiveness of our proposed algorithm.

Skyline is an important operation in many applications to return a set of interesting points from a potentially huge data space. Given a table, the operation finds all tuples that are not dominated by any other tuples. It is found that the existing algorithms cannot process skyline on big data efficiently. This paper presents a novel skyline algorithm SSPL on big data. SSPL utilizes sorted positional index lists which require low space overhead to reduce I/O cost significantly. The sorted positional index list Ljis constructed for each attribute Ajand is arranged in ascending order of Aj. SSPL consists of two phases. In phase 1, SSPL computes scan depth of the involved sorted positional index lists. During retrieving the lists in a round-robin fashion, SSPL performs pruning on any candidate positional index to discard the candidate whose corresponding tuple is not skyline result. Phase 1 ends when there is a candidate positional index seen in all of the involved lists. In phase 2, SSPL exploits the obtained candidate positional indexes to get skyline results by a selective and sequential scan on the table. The experimental results on synthetic and real data sets show that SSPL has a significant advantage over the existing skyline algorithms.