Trajectory Data Mining for Road Network Updates and Route Deviation Detection

This article introduces how massive trajectory data collected from DiDi’s driver‑side app can be leveraged to improve travel experience by extracting key information for road‑network updates and route‑deviation detection.

Background : Data mining (also known as Knowledge Discovery in Databases) involves extracting patterns from large datasets using algorithms such as regression, classification, clustering, and pattern discovery. In practice, it is closely tied to big‑data technologies and requires domain knowledge. DiDi continuously uploads driver location data for dispatch, passenger‑driver meeting, navigation, and mileage billing, resulting in a wealth of trajectory data that reflects public road conditions and driver habits without violating user privacy.

Road‑Network Update : Intersections are critical nodes in digital maps. Frequent updates (new roads, geometry changes, topology errors) can cause mismatches in map matching, path planning, and navigation announcements. The paper proposes a three‑module framework—trajectory quality enhancement, intersection influence‑area detection, and topology calibration—presented at ICDE 2020.

1. Trajectory Quality Enhancement : Raw trajectories suffer from device errors and noise. The method segments trajectories based on spatial‑temporal continuity, filters dense noisy points, and applies the Douglas‑Peucker algorithm to compress while preserving turning features.

2. Intersection Position and Range Generation : A quadtree‑based spatial partition combined with Mean‑Shift clustering identifies core intersection cells. Speed analysis and direction‑based DBSCAN isolate candidate cells; Mean‑Shift then refines the intersection center.

3. Topology Calibration : Detected intersection centers and ranges are expanded to collect all relevant trajectories. Turning clusters are extracted, centerlines are fitted, and map‑matched against the base road network. A direction‑weighted Fréchet distance and DBSCAN clustering improve similarity measurement for complex intersections.

Route Deviation Detection : The system addresses two scenarios—(a) “few‑and‑different” outlier routes (e.g., intentional detours) and (b) “many‑and‑different” collective deviations indicating road closures. Challenges include diverse route representations, sparse historical OD trajectories, and real‑time detection on TB‑scale data.

For outlier detection, the pipeline includes OD‑constrained trajectory modeling, density‑based clustering, and Minimum Description Length Partition compression. Navigation‑feature extraction (e.g., heading vs. OD angle) helps determine whether a driver is heading toward the destination.

For road‑closure detection, a Siamese LSTM with attention and a custom loss models traffic‑flow similarity, while a LSPD module quantifies pattern changes across OD spaces. The combined approach achieved high precision (≈70%) in detecting missing or shifted turning paths and is already deployed in DiDi’s production pipeline.

Conclusion : The work demonstrates how large‑scale trajectory mining, combined with machine‑learning and spatial‑analysis techniques, can continuously improve map quality, detect anomalies, and support real‑time safety products. Future work aims to platform‑ize these capabilities to lower the barrier for data‑driven insights across the organization.