An approach for the discovery and validation of urban mobility patterns

The increasing pervasiveness of mobile devices favors the collection of large amounts of movement data that can be analyzed to extract knowledge, i.e. patterns, rules and regularities, from user trajectories. In this paper we present TPM, an integrated algorithm which supports the overall trajectory pattern discovery process for detecting user's mobility behaviors. Specifically, the algorithm includes two main phases: (i) finding dense regions, more densely passed through ones; (ii) extracting trajectory patterns from those regions. Another contribution of the paper is a validation methodology for assessing the effectiveness of the TPM algorithm, e.g., evaluating how the discovered knowledge model fits to the input data it is discovered from. Such methodology represents a general solution that can be used to evaluate the accuracy of any algorithm aiming at extracting dense regions and trajectory patterns from GPS data. Furthermore, we propose novel trajectory similarity measures to evaluate the quality of the extracted patterns. A detailed experimental evaluation, performed by exploiting the proposed validation process, proves the efficiency and effectiveness of TPM.