A Mining Algorithm for Spatial-Temporal Trajectory Aggregation Patterns Based on r* Tree Index

Abstract

The invention relates to a spatio-temporal trajectory aggregation pattern mining algorithm based on R* tree index, comprising three steps of trajectory compression, trajectory clustering and aggregation detection. The algorithm comprehensively utilizes the motion direction, motion speed and offset information of the trajectory data to compress the trajectory and improve the compression effect of the algorithm; uses the line segment DBSCAN based on the R* tree index to cluster the trajectory segments to improve the efficiency of the algorithm clustering. Relevant experiments show that the algorithm has improved mining effect compared with similar algorithms. The next work is to apply this algorithm to the actual trajectory data aggregation pattern mining task to improve the effect of data mining.

Description

technical field [0001] The invention relates to the field of data mining, and mainly improves the spatio-temporal trajectory aggregation pattern mining algorithm Crowd-TAD (Crowd-Testand Divide) to improve the accuracy and efficiency of the aggregation pattern mining algorithm, and specifically relates to a spatio-temporal trajectory based on R* tree index Trajectory Aggregation Pattern Mining Algorithm. Background technique [0002] Spatial-temporal trajectory pattern mining refers to discovering useful behavior rules from the trajectory of moving objects to obtain valuable information. Among them, spatio-temporal trajectory aggregation mode mining mainly excavates dense moving object groups that last for a period of time within a certain spatial range, and is widely used in traffic forecasting and traffic route planning. [0003] Spatio-temporal trajectory aggregation patterns can be characterized according to the following factors: the shape or density of the moving grou...

AI Technical Summary

Problems solved by technology

The principle of the aggregation judgment algorithm based on the grid index is to establish a grid index at each time point to traverse the clustering set, and obtain the clustering set that needs to be calculated for distance, reducing the amount of calculation. The disadvantage is that the index efficiency is affected by the partition granularity

The principle of the aggregation judgment algorithm based on the R-tree index is to establish an R-tree index at each time point to store the minimum outsourcing rectangle of the cluster when calculating the distance between the clusters, and use the window query of the R-tree to perform pruning to reduce the distance between the clusters. The disadvantage of distance calculation is that the implementation of R tree is complicated, and the bounding rectangle does not necessarily approximate the shape of the cluster

The principle of the aggregation judgment algorithm based on the spatio-temporal graph is to establish a spatio-temporal graph based on the trajectory clustering information, and perform aggregation judgment based on the spatio-temporal graph. The disadvantage is that the time complexity is high. When the amount of data grows too fast, the scale of the spatio-temporal graph is large, and the efficiency of the mining algorithm is reduced.

[0005] There are still the following problems in the research of spatio-temporal trajectory aggregation pattern mining: first, the existing mining algorithms do not consider the motion direction attribute of moving objects, and cannot accurately reflect the dynamic characteristics of moving objects; second, the time complexity of the trajectory clustering process High, long running time, currently there is no optimal clustering scheme

Images