Online Clustering for Trajectory Data Stream of Moving Objects

Yanwei Yu1, 2, Qin Wang1, 2, Xiaodong Wang1, Huan Wang1 and Jie He1

  1. School of Computer and Communication Engineering, University of Science and Technology Beijing
    100083 Beijing, China
    yuyanwei0530@gmail.com
  2. Beijing Key Laboratory of Knowledge Engineering for Materials Science
    100083 Beijing, China
    wangqin@ies.ustb.edu.cn

Abstract

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.

Key words

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

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS120723049Y

Publication information

Volume 10, Issue 3 (June 2013)
Year of Publication: 2013
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Yu, Y., Wang, Q., Wang, X., Wang, H., He, J.: Online Clustering for Trajectory Data Stream of Moving Objects. Computer Science and Information Systems, Vol. 10, No. 3, 1293-1317. (2013)