Google Maps Timeline - How does the segmentation algorithm work?

Question

Google Timeline shows a very nice segmentation of my location history. It clearly identifies periods of time (i.e. segments) in which I stayed in the same location, and periods of time in which I moved from one location to another - ignoring the jitter that happens from GPS inaccuracy and small movements.

Does anybody know the algorithm that Google use for the segmentation? Can you suggest an algorithm that could do it, preferably with a link to an academic paper? We had some ideas of our own, but I would like to hear better suggestions that would consider things like GPS inaccuracy, slow movement, jitter, etc.

Notice that the algorithm is not a simple clustering algorithm, because it considers the order of the points - a sequence of points nearby is considered as staying in the same location, and the points between such sequences are considered as a movement from one place to another (I suppose the time gaps between points also has some effect).

Thanks!

Answer 1

You probably only need a simple filter and threshold approach.

1. Filter the data. Take the average position of the last 10 minutes.
2. Threshold: if the position changed by more than e.g. 50 meters, consider the user to be moving.
3. Filter again: Remove any too-short stationary or moving interval.

O(n) in complexity, as good as it gets.