The pervasive use of mobile devices and location-based services has supported the generation of large spatiotemporal datasets reflecting user movement behavior. However, studies on such type of data have depended heavily on geographic overlapping, and information about the time of day of travel visits has been overlooked. In this paper, we proposed an efficient method for mining user movement similarity based on users’ travel histories as recorded by GPS trajectories. Our approach also allowed consideration of related temporal effects. To that end, first we introduced a partition method to divide the trajectories into a set of line segments that allowed us to explore the correlation between users and their visited territories. Significantly, we proposed a characteristic point mapping method to transform the sparse GPS trajectories into a set of transactional data. Based on this data, we conducted a series of data mining procedures for efficient discovery of the users’ movement information. Second, we proposed a novel, lowrank matrix factorization-based method to cluster users’ movements into groups based on their similarity, including temporal characteristics. The experimental results demonstrated that the proposed method can be used to mine the popular roaming routes of users or similar movements efficiently while including temporal patterns. This approach can prove valuable for the development of location-based social network recommendations and human mobility prediction.