How to map a trajectory to a vector?

Question

I have a series of data points in this form (timestamp, lat, long) for a set of users. Each user has a trajectory when he travels from point A to point B. There might be any number of points from A to B. They are ordered data points based on time stamp. I want to transform them as a vector to do various analysis tasks. One thought I have is to look at turns and make them as a dimension. I would like to know more approaches. What I want is a one vector representing the whole trajectory, think of it like one point for a trajectory.Right now I have a collection of 3d points.

I would like to do trajectory similarity search. If there are two trajectories that in time are travelling close to each other then they are similar. Think of it like this you are going from house to work at 9am. Somebody else at 9:10 am also his home for work and stays some distance from you. Since u have the same workplace , you will most likely have same trajectory. Something like a classifier built on top of a trajectory. I can do activity detection in a trajectory, I can do a source destination analysis too.

Answer 1

I would start with dynamic time warping. As long as you have the distance between any two points (lat,long) this approach should work. It adjusts for different speeds of motion. For instance, you and I live in the same village and go to work to the same factory, but I stop by a coffee shop on the way. It takes longer for me to arrive but we're more or less on the same path, so the similarity measure adjusts for different time scales.

This is different from what you have in mind. It seems that you want to come up with one value (vector) to represent the trajectory, then calculate the distance between the vectors. I'm suggesting you to use the distance measure between the trajectories directly, without intermediate step.

Answer 2

If you only consider instantaneous turns, i.e., changes in direction, I don't think this will uniquely define the position at a next time instance -- unless each user is travelling at a constant known speed (no indication of this in your question). Since you are moving across a (spherical, I infer?) surface, you will probably need at least a second coordinate to determine you positions uniquely. Why not simply build the $2 \times N$ array $[\bf{x}(t); \bf{y}(t)]$ per user with time stamp as a parameter, then concatenate this to a $1 \times (2N)$ vector $[\bf{x}(t) \bf{y}(t)]$ you must have a vector (or $1 \times (2N\times M)$ for $M$ tagged users? You could also take arc length $s(t)$ for the travelled path as a parameter instead. Are the time stamps at regular intervals; otherwise you will need a separate vector for them for look-up. PS: I cannot see a link with stats; is this relevant to Cross Validated?

Answer 3

For each user, you have two time series, lat(t) and long(t). I think that's the simplest representation -- I wouldn't try to complicate things by converting to some definition of turns, which would not only be more difficult, but also would require being very careful about the initial starting point and treating it differently in any analysis. (It's probably noisier as well.)

Keeping the data as lat & long time series also keeps it simple for the most likely use -- where you will look at a various time windows at different times - there's no need to constantly recalculate a starting point at the beginning of a new time window being analyzed.

If every users' time series lat & long were all sampled at the exact same times, as noted in another reply you can just concatenate the two time series vectors into one long vector. A similar example that had 5 time series looked like this:
. Then you have one long vector for each user that you can analyze just like any other vector for pattern recognition, distance measures, clustering, etc.

For distance measures between users, you're typically going to use a weighted form depending on the application. For instance, when focusing on convergence towards a common destination, you'd increase the weights the most towards the end of the time window (whether looking at euclidean calculations, max distance, etc.).

But, the original question seems to say that there may be differing numbers of points between A and B for different users. And in any case, even for the same sampling interval, it's likely that that the times aren't exactly the same (maybe differing by some constant because sampling started at different times). Furthermore, it's quite possible that there will be some missing data. In any of these cases, conceptually, you'd need to think of each time series in continuous form, perhaps fitting a curve to it, and resampling every user at the exact same times. (That's analogous to the resampling that occurs in photo analysis when you shrink a picture). Then your time series vectors for lat & long are the same length and correspond exactly to the same times, so that the concatenated vectors for each user over some time period can be compared to each other correctly.