Consider the problem of wanting to extract semantically coherent 'tracks' from a sequence of GPS readings.

In this context, I mean 'semantically coherent' to be arbitrary and subjective. For example, consider the Moves App: it's a mobile app which sits on a smartphone and reads the GPS position at a somewhat constant rate. Afterwards, it generates a 'timeline' of sorts from the readings into understandable segments, such as:

What are the methods/algorithms available to create such segments?

Currently, I use a naive ad hoc algorithm: 'replay' the measurements, adding them to the current segment, start a new segment if next position is too far away in time and/or space from the end of the current segment. I have moderate success with this approach, but this makes it too sensitive to outlier points and is not very prone to parallelisation in this form.


The keyword to search for is sessionization.

The problem of sessionization is very common in "big data" and user analytics, where it may be of interest to take a stream of events (such as actions on a website) and group them into sessions based on some criteria (most usually, timeout criteria - if a user does nothing for over X minutes, their next action is considered to be in a separate session).

The algorithm described in the question is basically the way to do it. To leverage parallel processing, there are a couple options:

1) Parallelize by user: each parallel task will process only the events of a certain user. This is straightforward to do with MapReduce (map emits user key by event, reduce runs this algorithm on events of a single user). This works well if there are many users and they are not too disbalanced.

2) Parallelize by user and time window: The same idea, but now time is introduced - the key is now (user, day) instead of just (user). This enables more granular tasks and presumably better gains with parallelization (especially if there are not too many users). The drawback now is that sessions may be 'cut' in the middle if they span more than one time window. For example, if a session starts at 11 PM and ends at 1 AM, two sessions would be generated if the time window is 'day' (11 PM - 0 AM and 0 AM - 1 AM).

The parallelization can be taken even further by adding the ability to merge two sessions. If the result of option 2 is passed through another process which looks at the all sessions of a single user, this process can order the sessions and look at the end point of one session and the start point of the next, possibly merging them together and emitting a single session. This is somewhat what frameworks like Apache Flink do, at a high-level.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.