A Framework for Group Converging Pattern Mining using Spatiotemporal Trajectories

A group event such as human and traffic congestion can be very roughly divided into three stages: converging stage before congestion, gathered stage when congestion happens, and dispersing stage that congestion disappears. It is of great interest in modeling and identifying converging behaviors before gathered events actually happen, which helps to proactively predict and handle potential public incidents such as serious stampedes. However, most of existing literature put too much emphasis on the second stage, only a few of them is dedicated to the first stage. In this paper, we propose a novel group pattern, namely converging, which refers to a group of moving objects converging from different directions during a certain period before gathered. To discover efficiently such converging patterns, we develop a framework for converging pattern mining (CPM) by examining how moving objects form clusters and the process of the cluster containment. The framework consists of three phases: snapshot cluster discovery phase, cluster containment join phase, and converging detection phase. As cluster containment mining is the key step, we develop three algorithms to discover cluster containment matches: a containment-join-algorithm, called SSCCJ, by using spatial proximity; a signature tree-based cluster-containment-join-algorithm, called STCCJ, which takes advantage of the cluster containment relations and signature techniques to filter enormous unqualified candidates in an efficient and effective way; and third, to keep the advantages of the above algorithms while avoiding their flaws, we further propose a signature quad-tree based cluster-containment-join algorithm, called SQTCCJ, which can identify efficiently matches by considering cluster spatial proximity as well as containment relations simultaneously. To assess the proposed methods, we redefine two evaluation metrics based on the concept of Precision and Recall in the field of information retrieval and the characteristics of converging patterns. We also propose a new indicator for measuring the duration of the converging stage in a group event. Finally, the effectiveness of the CPM and the efficiency of the mining algorithms are evaluated using three types of trajectory datasets, and the results show that the SQTCCJ algorithm demonstrates a superior performance.