Milling Time-A ware Transit Patterns for Route Recommendation in Big Check-in Data

摘要

In current location-based services, there are numerous travel route patterns hidden in the user check-in behaviors over locations in a city. Such records rapidly accumulate and update over time, so that an efficient and scalable algorithm is demanded to mine the useful travel patterns from the big check-in data. However, discovering travel patterns under efficiency and scalability concerns from large-scaled location data had not ever carefully tackled yet. In this paper, we propose to mine the Time-aware Transit Patterns (TTP), which capture the representative traveling behaviors over consecutive locations, from the big check-in data. We model the travel behaviors among different locations into a Route Transit Graph (RTG), in which nodes represents locations, and edges denotes the transit behaviors of users between locations with certain time intervals. The time-aware transit patterns, which are required to satisfy frequent, closed, and connected requirements due to respectively physical meanings, are mined based on the RTG transaction database. To achieve such goal, we propose a novel TTPM-algorithm, which is devised to only need to scan the database once and generate no unnecessary candidates, and thus guarantee better time efficiency lower and memory usage. Experiments conducted on different cities demonstrate the promising performance of our TTPM-algorithm, comparing to a modified Apriori method.