Abstract
Similarity measurement is an important problem in trajectory analysis because it serves as a foundation for many applications, such as trajectory search, cluster- ing, and classi cation. Previously, most methods treat a trajectory as a sequence of points, and use point-to-point matching methods to measure the similarity of trajectories. In this thesis, we model a trajectory as a sequence of moving rect- angles along the time axis. Each moving rectangle creates an oblique rectangular column, aka a cuboid, in the three dimensional space spanned by the x-y axes and the time domain. The volume of the intersection between the cuboids formed from two sequence of moving rectangles is used as the similarity measurement between two trajectories. We developed an effective algorithm, called Moving Rectangle In- tersection Detection (MRID), to calculate the intersections. MRID runs linear time in terms of number of trajectory points, and can be integrated with trajectory com- pression algorithms to achieve even faster execution time. Experiments that use real GPS data show that MRID has better accuracy and performance than the Longest Common Subsequence (LCSS) method, which is a representative algorithm in the point based methods.