Mining place-matching patterns from spatio-temporal trajectories using complex real-world places

This paper introduces a place-matching pattern mining approach that detects place-matching patterns from raw spatio-temporal GPS trajectories using real-world places from OpenStreetMap. The approach begins by annotating raw trajectory recordings as either stopping or moving. It then groups contiguously stopping entries into so-called stop episodes; each of which is then associated with a number of potential stop place candidates from the real-world place repository OpenStreetMap. As each stop episode may have multiple place candidates, the proposed approach uses a Hidden Markov Model to probabilistically match each sequence of stop episodes to its most likely sequence of visited real-world places. The result of this stop episode formulation and place-matching is that the original trajectories are transformed into a discrete, greatly simplified, and more semantically meaningful sequence of place visitations. This format enables the last step of our approach where frequent itemsets and sequential patterns are extracted using traditional approaches. Experimental results with real and synthetic datasets demonstrate our approach's running time performance, robustness to GPS noise, dataset compression, and matching accuracy. Additionally, a case study using human trajectories from the real-world Geolife dataset reveals many interesting and seemingly real patterns. These findings suggest the general validity and applicability of our approach as a place-matching trajectory data mining approach