Real-World Complexity Of Central Trajectories

Abstract

When analyzing a set of trajectories, usually a very large amount of data is available. This dataset may be so large it makes full analysis impossible. A solution is to cluster the dataset into smaller subsets, and then to generate a representative trajectory for each subset, which represents the unique characteristics of the trajectories in the set. One way to do this is an algorithm called Central Trajectories, which generates a trajectory consisting of parts of the input trajectories and which is central relative to the trajectories in the set. This results in a trajectory that is relatively close to all other trajectories at all times. I analyze the complexity of the output of the algorithm, using multiple different methods and a large variety of real-world and synthetic datasets. The two main research questions are: “What is the real-world complexity of Central Trajectories?” and “What is the effect of path-simplification algorithms on the complexity of Central Trajectories?” The results suggest answer to the first question is that the complexity of the output is linear in the input, but the characteristics of the linear relationship between input and output vary depending on the characteristics of the dataset, in addition to the parameter epsilon of the Central Trajectory algorithm, which determines the maximum size of a discontinuity. Additionally, simplifying the output of Central Trajectories can greatly reduce the amount of vertices, since many redundant vertices are removed in the process.