TrajSplit: Scalable and Accurate Trip Extraction from Raw GPS Trajectories

The evolution of data-driven algorithms for trajectory analysis operations relies heavily on the availability of trajectory data. Unfortunately, most of the available trajectory datasets are not suitable for use by analysis operations. A main reason is that such trajectories are released in their raw form: A sequence of locations coming from the same device over a time period (e.g.: hours or years), whereas trajectory analysis operations need trip trajectories. Hence, existing trajectory analysis techniques preprocess the raw trajectories by applying simple rules to extract trips out of each trajectory. However, such basic rules miss too many realistic scenarios and result in low accuracy which negatively affects down-stream trajectory applications. This paper presents TrajSplit: an accurate and scalable algorithm for trip extraction from raw GPS trajectories. TrajSplit goes beyond the basic simple rules to introduce a realistic definition of a trip, which can be realized through a computationally expensive brute force approach. Therefore, TrajSplit offers two scalable heuristic approaches, that still achieve a very similar accuracy to its brute force. Experimental results, based on two real datasets, show that TrajSplit: (a) is far more accurate than the basic rules, and (b) is highly scalable when employing either of the heuristics.