doiSerbia

Online clustering for trajectory data stream of moving objects

Yu Yanwei (School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing, China + Beijing Key Laboratory of Knowledge Engineering for Materials Science, Beijing, China)
Wang Qin (School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing, China + Beijing Key Laboratory of Knowledge Engineering for Materials Science, Beijing, China)
Wang Xiaodong (School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing, China)
Wang Huan (School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing, China)
He Jie (School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing, China)

Trajectory data streams contain huge amounts of data pertaining to the time and position of moving objects. It is crucial to extract useful information from this peculiar kind of data in many application scenarios, such as vehicle traffic management, large-scale tracking management and video surveillance. This paper proposes a density-based clustering algorithm for trajectory data stream called CTraStream. It contains two stages: trajectory line segment stream clustering and online trajectory cluster updating. CTraStream handles the trajectory data of moving objects as an incremental line segment stream. For line segment stream clustering, we present a distance measurement approach between line segments. Incremental line segments are processed quickly based on previous line clusters in order to achieve clustering line segment stream online, and line-segment-clusters in a time interval are obtained on the fly. For online trajectory cluster updating, TC-Tree, an index structure, which stores all closed trajectory clusters, is designed. According to the linesegment-cluster set, the current closed trajectory clusters are updated online based on TC-Tree by performing proposed update rules. The algorithm has exhibited many advantages, such as high scalability to process incremental trajectory data streams and the ability to discover trajectory clusters in data streams in real time. Our performance evaluation experiments conducted on a number of real and synthetic trajectory datasets illustrate the effectiveness, efficiency, and scalability of the algorithm.

Keywords: trajectory stream clustering, density-based clustering, line segment cluster, trajectory cluster, TC-Tree, online