Mobile Intelligence

11.7 COMPARING MOVING OBJECT TRAJECTORIES

11.7.1 Distance Between Trajectories

To perform clustering or similarity searches on trajectories of moving objects, an appropriate definition of the distance (or similarity) between two trajectories is important. Typically, the trajectory of a moving object is represented as a sequence of consecutive locations in a two- or three-dimensional space, in contrast to the one-dimensional case, which is common in timeseries databases [33, 52]. In addition, distances for moving object trajectories should be robust to outliers since measurements in mobile environments are noisy and the movement of objects may contain “gaps.” Some distance measures proposed for moving object trajectories are investigated below.

For example, consider two trajectories of moving objects on the (x, y)-plane given as A = ((a_x,1, a_y,1),…, (a_x,n, a_y,n)) and B = ((b_x,1, b_y,1),…, (b_x,m, b_y,m)). Their lengths are n and m, respectively. When n = m, we can apply the Euclidean distance (L₂ distance), which is simple and also the most popular:

Although the Euclidean distance can be evaluated efficiently, it cannot be applied when two trajectories have different lengths.

11.7.2 Dynamic Time Warping (DTW)

It is often necessary to compute the similarity between two trajectories with different lengths. A well-known approach is to use dynamic time warping (DTW) [33, 52], which is ...