Efficient Algorithm for Calculating Similarity between Trajectories Containing an Increasing Dimension

P. Laurinen, P. Siirtola, and J. Röning (Finland)


data mining, trajectory similarity, algorithm, database


Time series data is usually stored and processed in the form of discrete trajectories of multidimensional measurement points. In order to compare the measurements of a query trajectory to a set of stored trajectories, one needs to calcu late similarity between two trajectories. In this paper an ef ficient algorithm for calculating the similarity is presented for a set of trajectories containing one increasing measure ment dimension, for example time series data. An even more efficient version of the algorithm suitable for situa tions where all dimensions are increasing, such as many spatio-temporal data sets, is also presented. Furthermore, the similarity measurement technique nearly fulfills the re quirements of a metric space, which is a clear improvement to the currently used procedure. The performance of the al gorithm is validated first by using data measured from a hot strip mill and then by using synthetically generated trajec tories. The new algorithm outperforms the currently used procedure by several orders of magnitude, depending on the context of usage.

Important Links:

Go Back