Sketching and Classifying Spatial Trajectories

Spatial trajectories, often represented as a sequence of spatial positions, are a standard way to represent human mobility patterns. They also are used to represent motion patterns including for animals, drones, or last-mile rentals (e-scooters). However, these trajectories are notoriously difficult to work with as they overlap and can stretch long distances.

In this talk we discuss a new sketch (the minDist Sketch) that makes just about any data analysis on trajectories tasks simple and efficient. This first considers spatial trajectories as an abstract shape, and then maps them to a high-dimensional Euclidean space as a vector. We can show recovery, pseudo-metric, and metric properties of this representation. Variants can include direction information, or traits like velocity and acceleration.

Moreover, once represented as this vector, the trajectory data is extremely easy to work with. Allowing for out-of-the-box use of software for nearest-neighbor search, clustering, and classification.

In particular, we conduct the first formal study of classifying spatial trajectories: given trajectories from two different distributions (e.g., generated by car or bus) given a new trajectory that is unlabeled, how well can we predict which class it was from?

Over several data sets we have assembled that demand this task, we conduct a large study, and show that the minDist sketch and its variants are consistently the easiest and most accurate method (or at the least among the best in each instance).

joint work with Pingfan Tang and Hasan Pourmahmood