Multi-level Similarity Sub-segment Matching Method for Spatiotemporal Trajectory

  Objectives  Trajectory subsegment matching is an important part of trajectory pattern mining. Its applications span many scenarios, such as user recommendation, abnormal movement detection and prevention of infectious diseases. Traditional trajectory matching methods are mainly based on classical distanc‍es or similarity measures, which are of high complexity and the accuracy is seriously affected by data noise.

  Methods  We firstly propose a multi-level trajectory code tree structure that integrates adaptive Hilbert geographic grid coding. A hierarchical organizational form and sub-segment subordinate relationship expression structure are formed from the entire segment of the trajectory to the smallest segment. Then a sub-segment similarity matching algorithm is designed based on the trajectory segment code tree to transform complex spatial calculation into string matching operation, which greatly reduces the computational complexity of similar matching of sub-segments.

  Results  Experiments on actual trajectory data show that the efficiency of the proposed method achieved more than an order of magnitude improvement over the classical distance-based similarity measurement method without affecting accuracy.

  Conclusions  We proposed trajectory subsegment matching method greatly reduce the computational complexity with acceptable accuracy, which has high application value in the field of multi-granulate trajectory pattern mining and similarity analysis.