A Novel Traffic Flow Reduction Method Based on Incomplete Vehicle History Spatio-Temporal Trajectory Data

Bowen Yang, Zunhao Liu, Zhi Cai, Dongze Li, Xing Su, Limin Guo, Zhiming DingISPRS Int. J. Geo Inf 2022 · DOI

TL;DR

This paper introduces a novel Trajectory Data Cube (TDC) model for storing and analyzing incomplete vehicle trajectory data, along with three hierarchical trace-back algorithms (HTB-p, HTB-v, HTB-KF) to restore missing position and velocity information. This approach aims to improve emergency path planning by providing more complete and accurate trajectory data, even with significant data loss.

What Problem Does This Paper Address?

Intelligent transportation systems rely heavily on vehicle trajectory data for various applications, from traffic planning and route recommendation to emergency management. However, real-world trajectory data is often incomplete due to signal loss, sensor malfunctions, or other environmental factors, leading to missing points or entire segments. This incompleteness significantly hinders the effectiveness of path planning and analysis. While existing methods exist for filling in missing trajectory information, they often require large datasets for training. This paper addresses the challenge of restoring trajectory data with a method that performs well even with limited training data, specifically focusing on improving emergency path planning by reconstructing incomplete vehicle histories.

Methods

The core of this work lies in two main components:

  • Trajectory Data Cube (TDC) Model: The authors propose a novel data structure called the Trajectory Data Cube. This model organizes spatio-temporal trajectory data (position, velocity, and time) hierarchically. It's designed to store data in time-based blocks, with each layer representing a specific time unit (e.g., day, hour). This structure allows for efficient storage and retrieval of trajectory information, even when dealing with sparse or incomplete data. The TDC also incorporates a "Topology Pointer" to link adjacent points, even if their spatial proximity isn't immediately obvious in the raw data.
  • Hierarchical Trace-Back (HTB) Algorithms: Three algorithms are introduced to restore missing trajectory information using the TDC:
  • HTB-p (Position Restoration): This algorithm focuses on restoring missing position data. It uses Bayesian conditional probability to infer the most likely position of a missing point based on its temporal proximity and known velocity information within the TDC.
  • HTB-v (Velocity Restoration): This algorithm aims to restore missing velocity information. It leverages the known position and time data, along with the TDC structure, to estimate the missing velocity using Bayesian probability.
  • HTB-KF (Position and Velocity Restoration): This algorithm combines the strengths of Kalman Filtering (KF) with the TDC model to restore both missing position and velocity information. It first uses KF to estimate missing positions and then uses the TDC to assign velocity based on the restored positions and temporal context.

Datasets

The experiments were conducted using real-world trajectory data from three major cities:

  • Beijing (BJ): 57 GB of taxi data from 2012-2013.
  • Shanghai (SH): 332 MB of taxi data from 2007.
  • New York (NY): 119 GB of yellow taxi trip records from 2019.

The New York dataset notably lacks velocity information, making it suitable for testing position restoration methods but not direct velocity restoration.

Key Insights and Ideas

  • TDC for Incomplete Data: The Trajectory Data Cube is a clever way to structure spatio-temporal data, making it more amenable to handling missing information by organizing it into time-based layers and linking related points.
  • Hierarchical Restoration: The HTB algorithms' hierarchical approach, leveraging both temporal and spatial context within the TDC, allows for more robust restoration compared to methods that only consider immediate neighbors.
  • Performance with Limited Data: A significant insight is the demonstrated effectiveness of the HTB algorithms, particularly HTB-KF, even when trained on a limited number of samples. This is crucial for real-world scenarios where obtaining large, complete datasets is challenging.
  • Velocity as a Key Indicator: The paper emphasizes the importance of velocity information for understanding traffic flow and restoring trajectory data, highlighting its role in inferring driving conditions.

Key Results

The paper presents several key findings from its experimental evaluations:

  • Position Restoration (HTB-p): HTB-p consistently outperformed KF and interpolation methods in terms of Mean Euclidean Error (MEE) across all three datasets (BJ, SH, NY). For instance, in Beijing, HTB-p achieved an MEE of 11.982 m, significantly lower than KF (26.470 m) and interpolation (27.529 m).
  • Velocity Restoration (HTB-v): HTB-v also showed superior performance in restoring missing velocity information, with error rates generally lower than KF and interpolation, especially in datasets with more continuous missing points. For example, in Shanghai, HTB-v achieved an error rate of 12.4% for a specific time point, compared to 21.0% for interpolation.
  • Combined Restoration (HTB-KF): HTB-KF demonstrated strong performance in restoring both position and velocity, achieving good results even with varying percentages of missing data and limited training samples. Figure 9 shows that HTB-KF and MDCGCN algorithms generally had better restoration effects as the percentage of missing data increased.
  • Robustness to Data Loss: The experiments indicated that HTB-KF maintained good restoration ability even when faced with a significant percentage of missing trajectory data (up to 30% in some experiments).

Limitations and Future Work

  • Deviation Angle: The authors acknowledge that the deviation angle of trajectory information is not currently considered as a factor. They propose incorporating this into future work to further enhance the completion of missing trajectory data, especially with limited training samples.
  • Sample Size: While the methods show promise with limited training data, the paper notes that the overall restoration effect can be influenced by sample size, as seen in the Shanghai dataset comparison.
  • Generalizability: The paper focuses on taxi trajectory data. Future work could explore the applicability of these methods to other types of vehicle trajectories or transportation modes.

Summary updated

BibTeX
@article{yang2022novel,
  author = {Bowen Yang and Zunhao Liu and Zhi Cai and Dongze Li and Xing Su and Limin Guo and Zhiming Ding},
  title = {{A Novel Traffic Flow Reduction Method Based on Incomplete Vehicle History Spatio-Temporal Trajectory Data}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2022},
  doi = {10.3390/ijgi11030209},
}
Figure