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.