A novel method of similarity search for moving object trajectories

An interesting issue in moving objects databases is to find similar trajectories of moving objects. Similar trajectories search highly depends on an efficient algorithm calculating similarity between two trajectories. The high complexity of existing methods, which is quadratic, interfere the promotion of the application. In this paper, we introduce a novel similarity function, Maximum Common Grid (MCG), of which the complexity is constant multiple of n. Our method divides the whole activity area of moving object into small regions, and then each trajectory is represented as a sequence of regions. We claim that the more two trajectories have Common Region, the more similarity they have. Common Region is defined as the region passed by both the two trajectories. Therefore we determine the similarity by the number of Common Regions between trajectories. The experimental results show that MCG is accurate and efficient.