TL;DR
This paper introduces a novel algorithm for identifying frequent user routes from GPS data by mapping trajectories onto a grid and using probabilistic methods to infer likely paths. Unlike previous methods, it can distinguish between routes in opposite directions and analyze sub-sections of trajectories, offering richer insights for applications like personalized advertising and public transport optimization.
What Problem Does This Paper Address?
Understanding how people move through their environment is crucial for various applications, from personalized services to urban planning. GPS devices have made it easier to collect detailed user trajectories, but extracting meaningful patterns from this noisy, often incomplete data remains a challenge. Existing methods often struggle with the inherent inaccuracies of GPS (e.g., signal occlusion, measurement errors), can't differentiate between routes taken in opposite directions (e.g., A to B vs. B to A), and lack the ability to analyze specific segments of a journey. This paper aims to address these limitations by developing a more robust and insightful approach to frequent trajectory mining.
Methods
The core of the proposed method involves transforming raw GPS data into a more structured representation.
- Grid Mapping: GPS data points are mapped onto a grid. The size of the grid cells is determined by the user's average speed, allowing for adaptive resolution.
- Probabilistic Trajectory Inference: For any two consecutive GPS points, the algorithm calculates potential intermediate paths. To manage the infinite possibilities, it limits the search to an elliptical area defined by the two points. Within this ellipse, it generates multiple candidate trajectories.
- Edge Crossing and Histogramming: Each candidate trajectory is analyzed to determine which grid edges it crosses. A probabilistic approach assigns a "crossing probability" to each edge based on the likelihood of a cell being occupied and the number of candidate crossings.
- Frequent Edge Identification: A histogram is built where bins represent grid edges and frequencies represent how many times each edge has been crossed across all trajectories. The algorithm then identifies the K most frequent edges.
- Frequent Path Generation: Combinations of these high-frequency edges are used to construct the most frequent user trajectories.
A key innovation is the ability to discriminate between routes in opposite directions and to analyze sub-sections of trajectories, which is achieved through the edge-based histogramming approach.
Datasets
The authors evaluated their algorithm on two datasets:
- Personal GPS Logging System: A dataset containing approximately 42 tracks from a car navigation system.
- CRAWDAD Dataset: A large dataset collected from over 523 taxis over one month in San Francisco, comprising over 10 million GPS points.
The CRAWDAD dataset required significant preprocessing to identify route start and end points, often by detecting periods when the taxi was parked.
Key Insights and Ideas
- Directionality Matters: The grid-based, edge-crossing approach naturally distinguishes between routes taken in opposite directions (e.g., Northbound vs. Southbound on the same road segment), a capability often missing in other methods.
- Sub-Section Analysis is Powerful: By focusing on frequently crossed edges, the algorithm can identify and analyze common sub-paths within longer trajectories. This is invaluable for applications that need localized insights, like targeted mobile advertising or understanding traffic flow on specific street segments.
- Probabilistic Interpolation Bridges Gaps: The probabilistic interpolation between GPS points helps to overcome data sparsity and measurement errors, providing a more complete picture of a user's movement even when GPS signals are weak or absent.
- Adaptive Grid Size: Using average speed to determine grid cell size allows the algorithm to adapt to different movement patterns, potentially improving accuracy and efficiency.
Key Results
The paper reports that their algorithm successfully identified frequent paths in their personal GPS data, matching manually determined ground truth. They also found that their method provided significant information about sub-paths, which was not achievable with the comparative algorithm. When tested against the algorithm proposed in [6] (Adaptive learning of semantic locations and routes), their approach demonstrated superior performance in distinguishing route directions and enabling sub-section analysis.
Limitations and Future Work
The authors acknowledge several limitations and suggest future directions:
- Computational Complexity: The computational time is dependent on dataset size and grid size. When high detail is required (small grid cells), the number of interpolating points can grow quadratically with the distance between measured points (O(L²)), leading to potential inefficiencies.
- Data Cleaning: The authors suggest that cleaning abnormal data points (e.g., GPS readings in the middle of the ocean) before running the algorithm could mitigate some computational issues.
- Hierarchical Interpolation: For cases with large time gaps between GPS readings (e.g., over 10 minutes), they propose a hierarchical interpolation mechanism to fill in missing segments more effectively.
- Mobile Phone Extension: They plan to extend the approach to mobile phones, adapting it for online processing to identify frequent routes in real-time.
Summary updated