Mining Trajectory Corridors Using Fréchet Distance and Meshing Grids

Abstract. With technology advancement and increasing popularity of location-aware devices, trajectory data are ubiquitous in the real world. Trajectory corridor, as one of the moving patterns, is composed of con-catenated sub-trajectory clusters which help analyze the behaviors of moving objects. In this paper we adopt a three-phase approach to dis-cover trajectory corridors using Fréchet distance as a dissimilarity mea-surement. First, trajectories are segmented into sub-trajectories using meshing-grids. In the second phase, a hierarchical method is utilized to cluster intra-grid sub-trajectories for each grid cell. Finally, local clus-ters in each single grid cell are concatenated to construct trajectory corridors. By utilizing a grid structure, the segmentation and concatena-tion need only single traversing of trajectories or grid cells. Experiments demonstrate that the unsupervised algorithm correctly discovers trajec-tory corridors from the real trajectory data. The trajectory corridors us-ing Fréchet distance with temporal information are different from those having only spatial information. By choosing an appropriate grid size, the computing time could be reduced significantly because the number of sub-trajectories in a single grid cell is a dominant factor influencing the speed of the algorithms