Discovering Real-Time Reachable Areas Using Trajectory Connections

The paper addresses the problem of real‑time reachable area analysis, where given a starting point and a time budget, the system returns the road segments that can be reached within that time considering current traffic conditions. Traditional static distance queries ignore dynamic traffic, and earlier methods either use static travel times or historical trajectories without accounting for real‑time conditions.

To overcome low coverage of recent trajectories, the authors propose a trajectory‑splicing technique that connects overlapping trajectories, improving reachable area estimation while controlling splicing depth (k) to balance coverage and reliability.

The solution framework consists of an offline learning phase that generates k‑value prediction labels from historical data and extracts spatio‑temporal features (traffic, time, weather, POI, road network), and an online phase that denoises and map‑matches incoming trajectories using the JUST platform, builds indexes, and predicts k for each query.

A novel Skip Graph Index (SG Index) is introduced, which retains only the fastest trajectories between any two points, forming a directed graph where nodes represent road segments and edge weights represent minimal travel time. This index transforms reachable area queries into k‑hop neighbor searches, enabling efficient pruning based on time cost and search depth.

For k‑value prediction, the authors generate training labels by comparing reachable areas obtained with different splicing depths against ground‑truth areas derived from a separate trajectory set, selecting the minimal k that satisfies coverage criteria. Five categories of features are extracted around the query point, and a Spatio‑Temporal Residual Network (ST‑ResNet) is employed to predict the optimal k.

Experiments on four real‑world datasets demonstrate the method’s accuracy and efficiency. Case studies show the approach captures real‑time traffic disruptions (e.g., a concert causing congestion) better than baseline methods, and performance tests reveal the SG Index with pruning (SGE+) achieves millisecond‑level query response times, outperforming other indexing techniques.

References to the original DASFAA 2020 paper, related patents, and supplementary materials (PDF, PPT, demo link) are provided.