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.

Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. Given a set of weighted objects, this query aims to find an optimal location from a candidate set to maximize itsinfluence, which is the total weight of its reverse nearest neighbors. Existing work commonly assumes that every object is in a fixed location. In real life, however, there are a wide variety of drive-in services (e.g., food joints, pharmacies, ATMs, etc.) that are widely accessed by mobile users (i.e., trajectories) instead of the fixed ones. In this paper, we first define the Maximizing Influence query over Trajectories, namely, MIT query, which aims to find an optimal location to maximize the total weight of influenced trajectories. We propose a novel index, QB-tree to hierarchically group trajectories with similar activity regions together for subsequent unified processing, and classify trajectories inside the same node into multiple buckets according to their motion patterns. For each bucket, we construct a rectilinear polygon using the trajectories in it to exclude some irrelevant areas in the minimum boundary rectangle. Moreover, we develop a branch-and-bound approach called BBM to efficiently solve the MIT query. The algorithm adaptively partitions the candidates into disjoint regions and prunes the regions without containing optimal results. Then, by exploiting the QB-tree, the upper and lower bounds are efficiently computed with three-level pruning technique. Practically, we also study a variant of the MIT query, called MDT query. We propose novel pruning bounds in cooperation with QB-tree to answer MDT queries efficiently. Finally, extensive experiments on real and synthetic datasets demonstrate that our index and algorithms have high performance in terms of efficiency, scalability, and genericity.

Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. Given a set of weighted objects, this query aims to find an optimal location from a candidate set to maximize its influence, which is the total weight of its reverse nearest neighbors. Existing work commonly assumes that every object is in a fixed location. In real life, however, there are a wide variety of drive-in services (e.g., food joints, fuel stations, ATMs, etc.) that are widely accessed by mobile users (i.e., trajectories) instead of the fixed ones. It is urgent and challenging to solve the Max-Inf query in trajectory data (MIT). In this paper, we first define the MIT query which aims to find the optimal location to maximize the total weight of influenced trajectories. We propose a novel index structure, QB-tree to hierarchically group trajectories with similar activity regions together for subsequent unified processing, and classify trajectories inside the same node into multiple buckets according to their motion patterns. For each bucket, we construct a rectilinear polygon using the trajectories in it to exclude some irrelevant areas in the minimum boundary rectangle. Moreover, we develop a branch-and-bound approach called BBM to efficiently solve the MIT query. The algorithm adaptively partitions the candidates into disjoint regions and prunes the regions without containing optimal results. Then, by exploiting the QB-tree, the upper and lower bounds are efficiently computed with three-level pruning technique. Finally, we conduct extensive experiments on real and synthetic datasets to evaluate our index and algorithms, and the experimental results demonstrate that our algorithm has high performance in terms of efficiency, scalability, and genericity.

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.

Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal position of the rectangle to maximize the total weight of covered objects (i.e., Range Sum). All the existing literature for MaxRS query commonly assumes that every object is associated with a unique point. In real applications, however, every object (e.g., GPS-enabled moving vehicle) is related to a trajectory including a sequence of points, which goes beyond this restrictive assumption. How to tackle the problem of MaxRS query in trajectory data (MaxRST) is important and challenging. In this paper, we propose the definition of MaxRST query where a trajectory is covered by a rectangle if at least one of points in the trajectory is enclosed by the rectangle. We propose a novel method to solve MaxRST query by converting it to rectilinear polygon intersection problem. Then, an interval-tree-based partitioning technique is developed to efficiently settle rectilinear polygon intersection problem. To further shorten the response time, we present ($\epsilon, \delta$) -approximate MaxRST query, which returns an approximate answer having the relative error$\epsilon$to the optimal covered weight with probability at least$\delta$. Furthermore, two complementary sampling-based ($\epsilon, \delta$) -approximate MaxRST algorithms are proposed. One performs random sampling with replacements on rectilinear polygons and the sample size is irrelevant to the number of trajectories. The other employs grid shifting technique to reduce sample size yet requires an extra cost for grid construction. The theoretical analysis and experimental results show that our proposed algorithms have high performance in terms of efficiency and accuracy.

Battery-free wireless sensor networks (BF-WSNs) extend the lifetime of wireless sensor networks (WSNs) using ambient energy sources. Thus, it becomes an emerging research area of Internet of Things (IoT) in recent years. Although many existing works in this area study data collection, few of them focus on optimizing the latency of data collection. In this article, we propose a novel distributed framework (DCF) for low-latency data collection in BF-WSNs. DCF uses an adaptive routing strategy, so battery-free nodes can select receivers depending on their status. It also provides transmitting opportunities for as many nodes as possible in each time slot to achieve high spatial parallelism. We also propose two strategies embedded in DCF to generate local schedules. These strategies allow nodes to determine their schedules based only on information from neighboring nodes. We then analyze the theoretical latency bounds of DCF with and without algorithm parameters, respectively. By comparing with the bound of the existing method, we conclude that the latency bound of DCF is superior. Finally, extensive simulations show that DCF significantly outperforms the existing method.

The skyline query is important in the database community. In recent years, the researches on incomplete data have been increasingly considered, especially for the skyline query. However, the existing skyline definition on incomplete data cannot provide users with valuable references. In this paper, we propose a novel skyline definition utilizing probabilistic model on incomplete data where each point has a probability to be in the skyline. In particular, it returns K points with the highest skyline probabilities. In addition, we propose incomplete models and estimate probability density functions of missing values on independent, correlated, and anti-correlated distributions, respectively. Meanwhile, it is a big challenge to compute probabilistic skyline on incomplete data. We propose three efficient algorithms SPISkyline, SPCSkyline, and SPASkyline for probabilistic skyline computation on incomplete data complying with independent, correlated, and anti-correlated distributions, respectively. They employ pruning strategy, optimization of the process of probability computation, and sorting technique to improve the efficiency of probabilistic skyline computation on incomplete data. Our experimental results demonstrate that our proposed concept of probabilistic skyline is an effective method to tackle skyline query on incomplete data and our algorithms are tens of times faster than the naive algorithm on both synthetic and real datasets.

The skyline query is important in database community. Recently, owing to the inherent uncertainty of some applications, skyline query on uncertain data has been widelystudied using probabilistic model, e.g. p-skyline. In the scenario where uncertain data is vertically distributed among multiple servers, the main purpose of p-skyline computation is to minimize the retrieved records from servers to the local client due to the dominance factor of expensive network communication. In this paper, we present three communication-efficient p-skyline algorithms ASR, IASR and FSLR on vertically distributed uncertain data. ASR alternates sorted and random accesses to retrieve the records at servers and performs retrieving-boundingchecking iteration until all the objects can be determined whether they are in the p-skyline result or not. The communication of the instances not retrieved can be saved. IASR is an improved version of ASR. By examining the net gain of retrieving-boundingchecking iteration, IASR early terminates the iteration to further reduce the cost of communication. Compared to ASR and IASR, FSLR performs random accesses only on demand. FSLR first conducts sorted accesses to get loose upper bounds of skyline probabilities of the instances. Then, FSLR uses random accesses to complement a part of retrieved instances to get tighter upper and lower bounds of skyline probabilities until the p-skyline result is computed. Our experimental results demonstrate that our algorithms ASR, IASR and FSLR significantly outperform the intuitive method for p-skyline computation on vertically distributed uncertain data.

The skyline query is important in database community. In recent years, the researches on incomplete data have been increasingly considered, especially for the skyline query. However, the existing skyline definition on incomplete data cannot provide users with valuable references. In this paper, we propose a novel skyline definition utilizing probabilistic model on incomplete data where each point has a probability to be in the skyline. In particular, it returnsK points with the highest skyline probabilities. Meanwhile, it is a big challenge to compute probabilistic skyline on incomplete data. We propose an efficient algorithm PISkyline, which utilizes two pruning strategies to reduce the number of points and adopts two optimizations to accelerate probability computation for each point. Nevertheless, PISkyline is susceptible to the order of input data and there is still a great deal of room for optimization. We develop a point-level sorting technique by adjusting the order of accessing points to further improve the efficiency of PISkyline. Our experimental results demonstrate that our algorithms are tens of times faster than the naive algorithm on both synthetic and real datasets.