Analyzing Trajectories Using Uncertainty and Background Information

Abstract

A key issue in clustering data, regardless the algorithm used, is the definition of a distance function. In the case of tra jectory data, different distance functions have been proposed, with different degrees of complexity. All these measures assume that tra jectories are error-free, which is essentially not true. Uncertainty is present in tra jectory data, which is usually obtained through a series of GPS of GSM observations. Trajectories are then reconstructed, typically using linear interpolation. A first source of error in tra jectory are the GPS observations themselves, since many reported points lie outside the road network. Thus, the users position must be matched to a map, leading to the problem of map matching. A well-known model to deal with uncertainty in a trajectory sample, uses the notion of space-time prisms (also called beads ), to estimate the positions where the object could have been, given a maximum speed. Thus, we can replace a (reconstructed) trajectory by a necklace (intuitively, a a chain of prisms ), connecting consecutive trajectory sample points. When it comes to clustering, the notion of uncertainty requires appropriate distance functions. The main contribution of this paper is the definition of a distance function that accounts for uncertainty, together with the proof that this function is also a metric, and therefore it can be used in clustering. We also present an algorithm that computes the distance between the chains of prisms corresponding to two trajectory samples. Finally, we discuss some preliminary results, obtained clustering a set of trajectories of cars in the center of the city of Milan, using the distance function introduced in this paper.