Mining converging patterns over streaming trajectories of moving objects in road networks

A converging pattern represents the process in which a collection of moving objects gradually converges toward a target area from various directions and eventually forms a dense group. Unlike most existing group patterns, it indicates the early formation of group events, which has a significant application for predicting and detecting emergency events. Existing studies of the converging pattern merely discover patterns from historical trajectories in an offline manner. However, online mining over streaming trajectories has a more practical impact in some real-world scenarios like real-time traffic monitoring . In this paper, we investigate online algorithms that enable converging pattern mining over network-constrained streaming trajectories of moving objects. To achieve synchronization with the speed of trajectory updates, we propose an incremental density-based clustering algorithm in the road network called I D C R N and a converging monitoring method to detect converging patterns in real-time. To efficiently retrieve the constantly evolving spatial relationship among objects in road networks with a large search space and an intractable computation complexity for network distance, we propose a dual index called M O R N to support continuous neighborhood query and cluster pruning in the road network . Extensive experiments with real and synthetic datasets validate the efficiency of our proposed index and methods.