Network Topology Aware Moving Object Trajectory Clustering
This paper illustrates a three step clustering method for moving object trajectories to discover common sub paths. The proposed algorithm (TOPOSCAN) is inspired from the well known partition and group framework and density based algorithms. It takes advantage of topological relation of a predefined network, and reduces the dimension of trajectory databases and algorithm complexity. TOPOSCAN consists of three steps: network topology construction, trajectory mapping, and path clustering. For network topology construction, we define the network as a directed graph, associated with a network attribute table to describe link relationships. For the trajectory mapping, the authors adopt a map matching algorithm to assign trajectory points to network links. For the path clustering, the authors develop a framework with extraction, extension and exclusion steps to select the common sub paths. TOPOSCAN is implemented using simulated trajectory data. The experimental results demonstrate that TOPOSCAN correctly and efficiently discovers common sub paths from vehicle trajectory data. The recognized patterns are useful for transport management and operation design.