Online clustering of trajectory data stream

Abstract

Mining trajectory patterns allows characterizing movement behavior (i.e. congestion, flocks, swarms, leadership, among others), which leverages new applications and services. Movement tracking becomes ubiquitous in many applications, which raises great interests in trajectory data analysis and mining. Most existing approaches allow characterizing the past movements of the objects but not current patterns, because they use only historical trajectory data. Recent approaches for online clustering of moving objects location are restricted to instantaneous positions. Subsequently, they fail to capture moving objects' behavior over time. By continuously tracking moving objects' sub-trajectories at each time window, rather than just the last position, it becomes possible to gain insight on the current behavior, and potentially detect mobility patterns in real time. Real-time analysis of mobility data may offer novel tools to better understand ongoing city dynamics, as well as the detection of regularities and anomalies as they happen; all in all, this can represent an invaluable tool when tackling decision-making tasks. Among the possible patterns, in this thesis we mainly consider (sub)-trajectory clustering and its evolution. Discovering such patterns may help to re-engineer effectively the traffic within a city, or to promptly detect events at the city level (e.g., car accidents) as they happen. In the first line of investigation we tackle the problem of discovering and maintaining the density based clusters in trajectory data streams in Euclidean Space, despite the fact that most moving objects change their position over time. We propose CUTiS, an incremental algorithm to solve this problem, while tracking the evolution of the clusters as well as the membership of the moving objects to the clusters. Our experiments were conducted on two real datasets and the experiments show the efficiency and the effectiveness of our method comparing to two competitors DBSCAN and TraClus. As a second line of research, we aim at improving the efficiency of the CUTiS algorithm. In this way, we propose an indexing structure for sub-trajectory data based on a space-filling curve. This approach has the property of mapping a multidimensional space to one-dimensional space such that, for two objects that are close in the original space, there is a high probability that they will be close in the mapped target space. We take advantage of this property to optimize range queries from a moving object sub-trajectory on the incremental clustering algorithm. Our experiments were conducted on a real data set and they show the efficiency and the effectiveness of our method compared to our previous proposed CUTiS, DBSCAN and TraClus. As a third line, we investigate the same problem of sub-trajectory clustering discovery and maintenance on a Road Network since many moving objects move on the road network in real applications. We propose Net-CUTiS an incremental clustering algorithm for road network constraint movement. The efficiency and effectiveness of Net-CUTiS were compared using a real dataset with NETSCAN and DBSCAN.