Similarity search of time series trajectories based on shape

Abstract

Many researchers have been attracted towards searching of similar moving objects' trajectories due to their myriad applications. Similarity of trajectories is determined mainly by closeness or shape parameters. Closeness is measured by distance measures like Dynamic Time Warping (DTW), Edit Distance with Real Penalty (ERP), Edit Distance with Real Sequence (EDR) and Longest Common Subsequence (LCSS). These edit distance measures support scaling and translation property, but do not support rotation invariant property. Rotation Invariant (RI) distance measure supports all three properties and hence it is considered to be superior compared to other edit distance measures. However, it has two main drawbacks. The first one is, RI does not compares trajectories based on the shape. The second drawback is, RI is not robust to noise and hence produces poor results. In order to eliminate drawbacks faced by existing measures, in this paper, we have proposed Polygon Based Distance (PBD) measure to compare trajectories for similarity. Our proposed PBD distance measure supports scaling and translation properties like other measures. The main advantages of PBD distance measure are, it is invariant of rotation, it compares the trajectories based on the shape and it is robust to noise. We have performed experimental study on real time and synthetic datasets. The average accuracy of DTW is 21.67, RI is 35 and PBD is 58.33. Since PBD measure compares the trajectories based on shape and is robust to noise, its accuracy is higher compared to DTW and RI distance measures.