Discovery of evolving companion from trajectory data streams

The widespread use of position-tracking devices leads to vast volumes of spatial-temporal data aggregated in the form of the trajectory data streams. Extracting useful knowledge from moving object trajectories can benefit many applications, such as traffic monitoring, military surveillance, and weather forecasting. Most of the knowledge gleaned from the trajectory data illustrates different kinds of group patterns, i.e., objects that travel together for some time. In the real world, the trajectory of the moving objects can change with time. Thus, existing approaches can miss a new pattern because they have a stringent requirement for moving object participators in a group movement pattern. To address this issue, we introduced a new type of moving object group pattern called an evolving companion. It allows some members of the group to leave and join anytime if some participators stay connected for all time intervals. In this pattern discovery, we model an incremental discovery solution to retrieve the evolving companion efficiently over the data stream. We evaluated the efficiency and effectiveness of our approach on two real vehicles and one synthetic dataset. Our method performed well compared with existing pattern discovery methods; for example, it was about 50% faster than Tang et al.'s buddy-based clustering method.