Optimization Of Co-movement Pattern Computation For Large-scale Trajectory Streams

The popularity of mobile devices and the development of precise positioning technology make trajectory data easier to collect,bringing new opportunities for behavior analysis based on trajectories.Spatiotemporal trajectory pattern mining plays an important role in fields such as urban traffic optimization and tourism route planning,and has significant research value,but the large-scale similarity calculation involved is a huge challenge.This article focuses on a general framework for discovering accompanying patterns and designs an index optimization method to mine spatial proximity groups.Based on the group discovery results,the object’s movement pattern is cross-checked to achieve pattern detection of billions of trajectory points.Optimizations were designed for clustering and cross-computation in pattern mining,and the main work is as follows:(1)An adaptive partitioning algorithm(AP)was designed to improve the computation cost of data partitioning and cross-border data replication,while ensuring data integrity.The algorithm combines uniform grid partitioning and adaptive extended partitioning algorithms to output trajectory data to an orderly storage collection according to latitude and longitude,and evenly divide the collection based on the distribution of boundary points.The grid boundary is adaptively extended based on the distribution of boundary points,effectively handling trajectory points that cross grid boundaries and avoiding data loss.Experimental results show that the AP method can effectively balance the load of data partitioning,ensuring high availability and accuracy of the data.(2)A trajectory-based clustering algorithm called calibrated clustering algorithm(CCA)based on VP-Tree was proposed to effectively solve the high computation cost of spatial proximity search in trajectory accompanying pattern mining and accelerate the discovery speed.Compared to traditional density clustering algorithms,the CCA algorithm provides faster group mining calculation for distributed trajectory stream accompanying pattern mining frameworks.The algorithm organizes the real road network using a tree-shaped index structure based on spatial distance measurement and uses a nearest neighbor search algorithm to search for the closest combination.During the nearest neighbor search,the instantaneous movement direction between trajectory objects and the matching of the direction at the alignment intersection are considered to adjust to the best fitting alignment point,accurately aligning the trajectory points in the trajectory stream to the real road network.The aligned trajectory points are organically organized in the VP-Tree,and the nonleaf node index structure is used to replace traditional density clustering to provide spatial proximity clusters for accompanying patterns.Experimental results show that compared to previous density clustering algorithms,the CCA algorithm has better time performance in mining spatial proximity groups,with a performance improvement of an order of magnitude.(3)A distributed pattern enumeration and verification algorithm,Parallel Pattern Analysis and Mining(PPAM),was proposed along with a framework for co-movement pattern mining based on highly concurrent trajectory streams(FCMPHTS).The framework is built on the distributed stream computing engine,Flink,to improve the efficiency of comovement pattern discovery.The PPAM algorithm distributes spatial neighbor groups and broadcasts candidate co-movement patterns to multiple nodes,allowing parallel matching operations to be performed across nodes.Compared to existing algorithms that perform pattern matching on a single node,the PPAM algorithm reduces the time consumption of the pattern matching phase.The FCMPHTS framework integrates the AP,CCA,and PPAM algorithms,fully exploiting the stream processing advantages of Flink and showing better performance in co-movement pattern mining than existing frameworks.Experimental results show that compared to traditional density-based clustering algorithms for spatial neighbor group mining,FCMPHTS reduces time consumption by 40%～50% during the spatial neighbor search phase,and compared to existing distributed frameworks,it reduces time consumption by 20%～30%.