Spatial Movement Pattern Discovery with LCS-based Path Similarity Measure

摘要

Location-enhanced applications are a rapidly emerging area of ubiquitous computing. They are starting to achieve mass adoption in people's everyday life. Moving objects can be tracked with navigation and orientation sensors such as GPS devices or RFID tags. Their movements can be represented as sequences of time-stamped locations. Studying such spatio-temporal movement series to discover spatial sequential patterns holds promises in many real-world settings. A few interesting applications of such kind are vehicle travel pattern discovery and travel route prediction, or customer shopping traverse pattern discovery. Traditional spatial data mining methods suitable in Euclidean space are not directly applicable for these sequential settings. We propose a Longest Common Subsequence (LCS)-based algorithm to cluster movement trajectories for travel pattern discovery. Experiments are performed on a GPS trace dataset of vehicle travel trajectories in Athens, Greece. We visualize the clustering results and compare them with a baseline outcome using Google Earth. The evaluation results show that the proposed LCS-based approach can be used to support effective pattern discovery for moving object travel trajectories.