Due to the widespread availability of GPS devices, a large amount of trajectory data can be collected. These data come in the form of unbounded streams, called trajectory streams. Many applications like urban planning, transportation, and ecology benefit from performing spatial queries on these data, but due to the Big Data size, spatial indexes need to be built to process queries efficiently. Existing systems for trajectory stream data management and analytics do not exploit the online, continuous behavior of trajectory streams for indexing, leading to wasted time. In this paper, we introduce PIMMLI, a Spark-based trajectory stream query processing algorithm that avoids re-indexing spatial data with the arrival of each new batch of points by forecasting the trajectories, expanding their Minimum Bounding Rectangles accordingly. Our experiments on a real-life dataset show that PIMMLI has comparable query execution time with competitors while having up to 29% savings in indexing time.

A data stream is an infinite sequence of data points generated from a source continuously at a fast rate, which is characterized by the transiency of the data points, the temporal relationship among the data points, concept drift, and multi-dimensionality of data points. Outlier detection in data streams thus needs to deal with the characteristics of Big Data applications such as volume, velocity, and variety. The problem of detecting outliers in multiple concurrent data streams introduces additional challenges to the problem. In this paper, we propose a parallel outlier detection technique CODS to detect Contextual Outliers in multiple concurrent independent multi-dimensional Data Streams using a Graphics Processing Unit (GPU). The proposed algorithm addresses all the aforesaid characteristics of data streams. A set of experiments demonstrates reasonable outlier detection accuracy and scalability of CODS with the number of data streams.

Cloud database providers provision different architectures to guarantee high availability. One of these architectures is a cluster database that consists of several database engine nodes, where data is replicated among the nodes. Although the cloud database providers provide various auto-indexing tools, these tools mostly address characteristics of a database deployed on a single node, not a cluster. It is possible to install an index advisor on each node, which recommends an index set for that node. The problem with this approach is that the current index advisors for a single node aim to minimize the processing cost of the workload; however, on a cluster database, other goals such as load balancing can be considered. Hence, the better solution could be an index advisor which has a comprehensive view of the cluster node.

Data mining techniques can be used in several significant types of research in various domains to understand the flows of data, discover hidden knowledge, and improve quality of life. Sequential pattern mining, which is one data mining method, has emerged in the transportation domain to recognize the dynamic behavior of vehicles, trains, people...etc. The idea of sequential pattern mining is to find the frequent subsequences in a database of sequences. Although multiple sequential pattern mining techniques can mine sequential patterns, timestamps are only used to order sequences and time between sequence events is ignored. This information is important in real applications, such as traffic recommendation system and transportation safety. Though knowing that measurement Y occurs after measurement X is valuable, it is more valuable to know the estimated time before the appearance of measurement Y, perhaps, for example, to schedule maintenance at the right time in order to prevent railway damages. In this paper, we propose an algorithm called Minits (MINIng Timed Sequential patterns) to find the frequent sequential patterns and include the transition time between events in these patterns. However, approaches that depend on serial architecture are not effective anymore due to the massive data that are frequently generated from different sources. Therefore, we exploit parallelism using multicore CPUs to improve the performance of Minits to handle big data. Extensive experiments on real and synthetic datasets are reported and show the significance and advantages of this approach. Also, the execution time using a multicore outperform the single core when it deals with big data.

DBSCAN is a density-based clustering algorithm that is especially useful for finding clusters of arbitrary shapes. As opposed to other clustering techniques, like K-means, it does not require the number of clusters to be specified as an input parameter, and it is highly robust to outliers. However, DBSCAN has a worst-case quadratic time complexity, which makes it difficult to handle large dataset sizes. To address this problem, several works have been proposed that exploit the massive parallelism of GPUs in DBSCAN clustering. Nonetheless, none of these works have been experimentally compared against each other. In this paper, we review the existing GPU algorithms for DBSCAN clustering and conduct the first experimental study comparing these GPU algorithms using three real-world datasets to identify the best performing algorithm. Our results show that CUDA-DClust is the best performing GPU algorithm in terms of execution time and memory requirements.

Nowadays, location-aware devices, such as GPS, provide a huge volume of spatial-temporal data. Analyzing the data to understand the behavior of objects (e.g. people) could be beneficial in many application areas. Due to the spatial and temporal nature and their complexity, researchers have developed various data mining techniques such as trajectory segmentation, which splits the trajectories into sub-trajectories, to prepare them for the mining step. A central issue in discovering knowledge is choosing an appropriate trajectory segmentation technique. In this paper, we provide a comparative study on two trajectory segmentation techniques, density-based and grid-based, when applied to sequential patterns discovery. We conducted experiments using two real-life datasets to evaluate the performance of the methods in terms of execution time and their impact on discovering the sequential patterns. The experimental results showed that the density-based is more efficient, while the grid-based is more effective.

With the increasing prevalence of location sensor devices like GPS, it has been possible to collect large datasets of a special type of spatio-temporal data called trajectory data. A trajectory is a discrete sequence of positions that a moving object occupies in space as time passes. Such large datasets enable researchers to study the behavior of the objects describing these movements by issuing spatial queries. Among the queries that can be issued are top-K trajectory similarity queries, which retrieve the K most similar trajectories to a given query trajectory. This query has applications in many areas, such as urban planning, ecology and social networking; however, this query is computationally expensive. In this work, we introduce a new parallel top-K trajectory similarity query technique for GPUs, FastTopK, to deal with these challenges. Our experiments on two large real-life datasets showed that FastTopK produces on average 107.96X smaller candidate result sets, and 3.36X faster query execution times than the existing state-of-the-art technique, TKSimGPU.

Data streams are sequences of data points that have the properties of transiency, infiniteness, concept drift, uncertainty, multi-dimensionality, cross-correlation among different streams, asynchronous arrival, and heterogeneity. In this paper we propose a new outlier detection technique for multiple multi-dimensional data streams, called Wadjet, that addresses all the issues of outlier detection in multiple data streams. Wadjet exploits the temporal correlations to identify outliers in each individual data stream, and after this, it exploits the cross-correlations between data streams to identify points that do not conform with these cross-correlations. Experiments comparing Wadjet against existing techniques on real and synthetic datasets show that Wadjet achieves 18.8× higher precision, and competitive execution time and recall.

A trajectory is a polygonal line consisting of the positions that a moving object occupies as time passes, and as such, it can be derived by periodically sampling the positions of the object. In this manner, and due to the proliferation of location-sensing devices, it has been possible to create large datasets of trajectories. Using these datasets it is possible to derive much information about the movement patterns of the objects. However, trajectory data is uncertain, and this can negatively impact the accuracy of data mining algorithms used to obtain the movement patterns of objects. One of the sources of trajectory uncertainty is the error inherent to GPS measurements, and another source relates to the fact that in practice many trajectories have sampling points that are on average too far in time, so it is difficult to determine its movement between points. In this paper, we propose a technique called TrajEstU that estimates the trajectory of a moving object in an unconstrained space. The algorithm is applied when there is uncertainty in trajectories due to measurement errors and/or low sampling rates. Experiments show that TrajEstU achieves up to 98% accuracy on real life and synthetic trajectory datasets.

Among many Big Data applications are those that deal with data streams. A data stream is a sequence of data points with timestamps that possesses the properties of transiency, infiniteness, uncertainty, concept drift, and multi-dimensionality. In this paper we propose an outlier detection technique called Orion that addresses all the characteristics of data streams. Orion looks for a projected dimension of multi-dimensional data points with the help of an evolutionary algorithm, and identifies a data point as an outlier if it resides in a low-density region in that dimension. Experiments comparing Orion with existing techniques using both real and synthetic datasets show that Orion achieves an average of 7X the precision, 5X the recall, and a competitive execution time compared to existing techniques.

There exist large datasets containing the sequences of points that moving objects occupy in space as time goes by. Such sequences of moving objects are known as trajectories. Being able to issue queries that allow the extraction of patterns from the movements of these objects is important to many real world applications, such as urban planning in transportation and bird migration tracking in ecology. One example of such queries is the top-K trajectory similarity query. This type of query receives as input arguments two sets P and Q of trajectories and a positive integer k, and seeks to find for every trajectory p in P the set of k trajectories in Q that are the most similar to p. However, querying these trajectory data is both compute and I/O intensive. In this paper we explore the potential of GPGPUs for supporting, in a scalable manner, top-K trajectory similarity queries. To this end, we propose an algorithm, called TKSimGPU, that incorporates parallelization strategies in order to answer this type of trajectory queries. We conducted experiments comparing the throughput of top-K trajectory similarity queries performed on multicore CPUs and GPGPUs using a large scale real world trajectory dataset. The experiments show that TKSimGPU achieved a 3.37x speedup in query processing time over exhaustive search on a GPU, and a 4.9x speedup in query processing time on a 12-core CPU architecture.