Online clustering for trajectory data stream of moving objects
Online clustering for trajectory data stream of moving objects
复制标题
DOI：
10.2298/csis120723049y
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yanwei Yu;Qin Wang;Xiaodong Wang;Huan Wang;Jie He
中科院分区：
文献类型：
--
作者：
Yanwei Yu;Qin Wang;Xiaodong Wang;Huan Wang;Jie He
轨迹数据流包含与移动物体的时间和位置有关的大量数据。在车辆交通管理、大规模跟踪管理和视频监控等许多应用场景中，从这种特殊的数据中提取有用的信息至关重要。本文提出了一种基于密度的轨迹数据流聚类算法，称为 CTraStream。它包含两个阶段：轨迹线段流聚类和在线轨迹聚类更新。 CTraStream 将移动物体的轨迹数据作为增量线段流进行处理。对于线段流聚类，我们提出了一种线段之间的距离测量方法。基于之前的线簇对增量线段进行快速处理，实现在线线段流的在线聚类，动态获取某个时间间隔内的线段簇。对于在线轨迹簇更新，设计了TC-Tree，一种存储所有闭合轨迹簇的索引结构。根据线段簇集合，通过执行建议的更新规则，基于TC-Tree在线更新当前闭合轨迹簇。该算法表现出许多优点，例如处理增量轨迹数据流的高可扩展性以及实时发现数据流中轨迹簇的能力。我们在许多真实和合成轨迹数据集上进行的性能评估实验说明了该算法的有效性、效率和可扩展性。
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.