Massively Parallel Discovery of Loosely Moving Congestion Patterns from Trajectory Data

Chunchun Hu, Si ChenISPRS Int. J. Geo Inf 2021 · DOI

TL;DR

This paper introduces "loosely moving congestion patterns" (LMCPs) to better capture real-world traffic congestion, which often involves vehicles moving together with similar directions but not necessarily strict spatial or temporal coherence. They developed a GPU-accelerated algorithm (PDCLUR) that efficiently discovers these patterns from large-scale trajectory data, achieving significant speedups over sequential methods.

What Problem Does This Paper Address?

Urban traffic management relies heavily on understanding traffic patterns. While existing methods can identify group movements like flocks or convoys, they often impose strict constraints on shape and temporal continuity, making them less suitable for capturing the nuances of traffic congestion. Traffic jams, for instance, can form and persist with vehicles moving in generally the same direction but with varying degrees of proximity and adherence to a rigid formation. The challenge is to efficiently discover these more flexible "loosely moving" congestion patterns from massive amounts of trajectory data to understand when and where congestion occurs.

Methods

The core of the paper is the introduction of the Loosely Moving Congestion Pattern (LMCP). An LMCP is defined as a sequence of spatial clusters of moving objects that maintain a similar direction of movement and a loose coherence over a specified duration. Unlike previous group patterns, LMCPs don't require strict shape preservation or continuous presence of the exact same objects.

To discover these patterns efficiently, the authors developed a parallel algorithm called PDCLUR (Parallel Equidirectional Cluster-Recombinant). This algorithm leverages GPU acceleration and builds upon the CLUR algorithm. The process involves:

  1. Spatial Clustering with Direction Limitation: Using a modified DBSCAN algorithm (PDL-DBSCAN) to identify spatial clusters of objects moving in approximately the same direction at each timestamp.
  2. Candidate Item Generation and Updating: Rules are defined to create new candidate LMCPs from these snapshot clusters and to update existing candidates by merging consecutive clusters that meet the LMCP criteria (common objects, similar direction, duration).
  3. LMCP Identification: Candidate patterns are finalized if they meet the minimum duration and coherence requirements.

The PDCLUR algorithm is designed for massive datasets by parallelizing the computationally intensive parts of the pattern discovery process across multiple GPU cores.

Datasets

The paper evaluates its approach using two real-world trajectory datasets:

  1. Shenzhen Taxi Trajectory Data: A smaller dataset (61,683 points from 1 day) used to test the sequential algorithm (Algorithm 1).
  2. Beijing Taxi Trajectory Data: A much larger dataset (approximately 33.9 million points from nearly 14,000 taxis over 24 hours) used to evaluate the performance of the GPU-accelerated PDCLUR algorithm.

The datasets contain vehicle ID, longitude, latitude, time, and speed. The paper notes that the Shenzhen dataset lacked explicit direction information, which was handled by default parameters.

Key Insights and Ideas

  • Looser Definition of Congestion: The concept of LMCP is crucial because real-world traffic congestion is rarely as rigid as traditional "flock" or "convoy" patterns. Vehicles can be part of a congestion event even if their exact paths or proximity vary slightly over time.
  • Directional Coherence is Key: The emphasis on "equidirectional" clusters is vital for identifying patterns that represent actual traffic flow and congestion, rather than just random groupings.
  • GPU Acceleration for Scale: The development of PDCLUR demonstrates the necessity of parallel computing (specifically GPU acceleration) to handle the sheer volume of modern trajectory data for meaningful analysis.
  • LMCPs Outperform Swarms for Congestion: The experimental results suggest that LMCPs are more effective than traditional "swarm" patterns for identifying actual congested road segments, providing a more accurate representation of traffic jams.

Key Results

  • Algorithm Effectiveness: The LMCP discovery algorithm successfully identified known congested road segments in both Shenzhen and Beijing, aligning with actual traffic conditions.
  • Performance Improvement: The PDCLUR algorithm achieved a significant acceleration ratio of over 65x compared to the sequential algorithm (Algorithm 1) when processing large datasets. For example, discovering patterns for ~4.34 million points over 28 days took only 352 seconds with PDCLUR, versus 24,056 seconds sequentially.
  • Accuracy: The accuracy ratio of discovered LMCPs was high, around 0.9 for mild congestion (under 30 km/h) and 0.8 for moderate congestion (under 20 km/h), indicating good reliability.
  • Qualitative Findings: The study identified specific congested road segments, congestion times (morning/evening peaks), and even directional patterns of traffic jams in Beijing. It also highlighted differences in congestion patterns between weekdays and weekends.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that choosing the "right" algorithm parameters (e.g., minOc, Tn, A) is crucial for discovering the most accurate congestion patterns and is an area for future research.
  • Single GPU Limitation: The current study focused on a single GPU. Future work will explore multi-GPU implementations and variable-grained domain decomposition strategies to further enhance performance.
  • Data Sources: The current approach primarily uses taxi trajectory data. Future work aims to integrate more diverse data sources, such as bus and other vehicle types, along with road network information (classification, capacity), to extract even richer patterns.

Summary updated

BibTeX
@article{hu2021massively,
  author = {Chunchun Hu and Si Chen},
  title = {{Massively Parallel Discovery of Loosely Moving Congestion Patterns from Trajectory Data}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2021},
  doi = {10.3390/ijgi10110787},
}
Figure