A study of quantitative and qualitative methods for trajectories

Abstract

In this work, we discuss two qualitative and two quantitative methods for similarity search for trajectories in R2xT. The two qualitative methods that are discussed are the Double{Cross and the Twisted{Cross and the quantitative methods are the Fréchet Distance and the Hausdorff Distance. Distance measures are very important in computer science, since they are, for example, used for similarity search, query by example and clustering. Before we start with this study, we will first take a look at the objects we like to compare: trajectories in R2xT. We will define and discuss them and give a definition and an algorithm to generalize these trajectories. Then we will give an explanation on how these different methods work, their differences and their similarities and their use in similarity search. The focus in this work, however, will be on the Fréchet{based Distance for trajectories: a new distance measure, inspired by the Fréchet Distance. We will give an algorithm for this new distance measure and we will prove that it stops and that it has an optimal running time. In the end, we will use the algorithm for the Fréchet{based Distance to calculate similarities between different trajectories and we will use it for clustering. All these tests are performed with our own program, designed to test these algorithms, named Algorithmtester. We will see that the algorithm returns excellent results with very little computational time needed.