Recently, clustering moving object trajectories kept gaining interest from both the data mining and machine learning communities. This problem, however, was studied mainly and extensively in the setting where moving objects can move freely on the euclidean space. In this paper, we study the problem of clustering trajectories of vehicles whose movement is restricted by the underlying road network. We model relations between these trajectories and road segments as a bipartite graph and we try to cluster its vertices. We demonstrate our approaches on synthetic data and show how it could be useful in inferring knowledge about the flow dynamics and the behavior of the drivers using the road network.
Approaches to trajectory clustering are mainly adaptations of existing algorithms to the case of trajectories. These include moving clusters @cite_10 , flock patterns @cite_7 , convoy patterns @cite_15 , the TRACLUS partition-and-group framework @cite_22 , etc. The aforementioned algorithms use euclidean-based similarities and distances and disregard the presence of an underlying network. Therefore, they can be used only in the case of unconstrained trajectories. The insightful idea of using a graph-based approach to cluster trajectory data was first introduced in @cite_19 . The approach is applied to free moving trajectories and considers the latter as sets of GPS points. Unlike our graph-based approaches, the authors do not rely on an underlying network as the basis of similarity calculations.
@cite_22 @cite_7 @cite_19 @cite_15 @cite_10
1981398125 2007159514 2120436185 2028618575
Existing trajectory clustering algorithms group similar trajectories as a whole, thus discovering common trajectories. Our key observation is that clustering trajectories as a whole could miss common sub-trajectories. Discovering common sub-trajectories is very useful in many applications, especially if we have regions of special interest for analysis. In this paper, we propose a new partition-and-group framework for clustering trajectories, which partitions a trajectory into a set of line segments, and then, groups similar line segments together into a cluster. The primary advantage of this framework is to discover common sub-trajectories from a trajectory database. Based on this partition-and-group framework, we develop a trajectory clustering algorithm TRACLUS. Our algorithm consists of two phases: partitioning and grouping. For the first phase, we present a formal trajectory partitioning algorithm using the minimum description length(MDL) principle. For the second phase, we present a density-based line-segment clustering algorithm. Experimental results demonstrate that TRACLUS correctly discovers common sub-trajectories from real trajectory data. Data representing moving objects is rapidly getting more available, especially in the area of wildlife GPS tracking. It is a central belief that information is hidden in large data sets in the form of interesting patterns, where a pattern can be any configuration of some moving objects in a certain area and or during a certain time period. One of the most common spatio-temporal patterns sought after is flocks. A flock is a large enough subset of objects moving along paths close to each other for a certain pre-defined time. We give a new definition that we argue is more realistic than the previous ones, and by the use of techniques from computational geometry we present fast algorithms to detect and report flocks. The algorithms are analysed both theoretically and experimentally. It is difficult to extract meaningful patterns from massive trajectory data. One of the main challenges is to characterise, compare and generalise trajectories to find overall patterns and trends. The major limitation of existing methods is that they do not consider topological relations among trajectories. This research proposes a graph-based approach that converts trajectory data to a graph-based representation and treats them as a complex network. Within the context of vehicle movements, the research develops a sequence of steps to extract representative points to reduce data redundancy, interpolate trajectories to accurately establish topological relationships among trajectories and locations, construct a graph (or matrix) representation of trajectories, apply a spatially constrained graph partitioning method to discover natural regions defined by trajectories and use the discovered regions to search and visualise trajectory clusters. Applications with a real data set shows that our new approach can effectively facilitate the understanding of spatial and spatiotemporal patterns in trajectories and discover novel patterns that existing methods cannot find. We introduce a convoy query that retrieves all convoys from historical trajectories, each of which consists of a set of objects that travelled closely during a certain time period. Convoy query is useful for many applications such as carpooling and traffic jam analysis, however, limited work has been done in the database community. This study proposes three efficient methods for discovering convoys. The main novelty of our methods is to approximate original trajectories by using line simplification methods and perform the discovery process over the simplified trajectories with bounded errors. Our experimental results confirm the effectiveness and efficiency of our methods.