Similarity Measure And Query On Spatiotemporal Trajectories

The similarity calculation of spatiotemporal trajectories quantifies the similarity features between trajectories,which is the basis for upstream similarity query and analysis of trajectory data.Effective and robust similarity measures along with their efficient calculation methods are also necessary prerequisites for many trajectory pattern mining applications.Explosive data volume,diversed data forms,and richer spatial and temporal embedded semantic information,all put forward higher requirements for similarity analysis methods and tools.Traditional research generally regards trajectories as linear objects consisting of point sequences.In essence,it is still based on the calculation and analysis of discrete spatial points,and cannot effectively grasp the unique properties of trajectory data such as time-ordered serializability,multi-granularity,and position uncertainty.Inview of the practical requirements of the military and related government departments on strategic and tactical intelligence analysis,public safety monitoring and early warning,and government decision-making assistance,this thesis systematically investigates the organizational structure and similarity analysis methods of multi-granularity trajectories from a new perspective of trajectory segments rather than discrete points.The research focuses on trajectory morphological similarity query,similarity measurement considering position uncertainty,and multi-granularity trajectory sub-segment similarity matching.The multi-granularity trajectory model and multi-level organizational structure with better expressiveness have been established.A more expressive multi-granularity trajectory model and multi-level organizational structure are established,a more efficient trajectory morphology similarity query algorithm is proposed,a more robust trajectory similarity measurement and a more accurate trajectory segment similarity matching method are designed.The specific research content is summarized as follows:(1)Universal multi-granular trajectory organization method based on adaptive meshing and coding.Aiming at the unified conceptual model and organizational management of multi-scale and multi-modal trajectories,this thesis designs a multi-granular spatiotemporal trajectory model(MGTM)on based on the analysis of existing trajectory data models.MGTM contains three levels of models from refined to coarse,i.e.,the spatiotemporal sequence model,the spatiotemporal segmentation model,and the start-end point model.MGTM describes the spatial morphology and semantic characteristics of trajectories at different granulates,achieving the fusion of the spatiotemporal and and moving characteristics of the trajectory.It provides a model basis for computing and mining similar patterns of spatiotemporal trajectories at different levels.Based on the current status of the global geographic grid subdivision model and existing standards,an adaptive grid coding method based on Hilbert geo-hashing is designed,realizing the integration and association of spatial data at the level of data organization and coding.The encoding realizes the dimensionality reduction processing of multiple types of spatial objects,which can be used as the organization and index structure.It can be used as the basis of spatial data partitioning and is also conducive to data distributed storage management with better spatial locality,providing support for refined trajectory organization and similarity calculation.(2)Trajectory morphology similarity query based on Fréchet distance threshold.There are numerous distance or similarity metrics of linear object,among which Fréchet distance is a classic one.The definition of Fréchet distance contains temporal relationship between sampling nodes by taking the sequence structure in the calculating process.Therefore,it can describe the similarity between trajectories more accurately even the trajectories contain fallback,ring or stagger.However,the computational complexity of Fréchet distance is relatively high and the query efficiency of trajectory shape similarity is relatively low.Addressing this problem,this thesis first reduces the size of the candidate set of similar trajectories by pre-filtering according to the specific characteristics of the trajectory shape characteristics,i.e.,the end-to-end points,the minimum bounding box,and the buffer.Afterwards,an ordered coverage judgment algorithm(OCJ)is designed to realize efficient similar trajectory query based on Fréchet distance threshold filtering.The algorithm is optimized in parallel using MPI/Open MP framework and Spark distributed computing platform.The query experiments on large-scale real trajectory datasets show that the OCJ algorithm and its parallel implementation have better computational efficiency and good parallel scalability.(3)An amended ellipse model and trajectory similarity measure considering position uncertainty and motion characteristics.Most measures of trajectory similarity in the literature are based on precise models that ignore the inherent uncertainty in trajectory data.Traditional computing or mining approaches that assume the preciseness and exactness of trajectories therefore risk underperforming or returning incorrect results.To address the problem,this thesis propose an amended ellipse model based on Bead-Prism model.it takes both interpolation error and positioning error into account.By computing the shape parameters of the ellipse dynamically based on motion features,each segment in a trajectory corresponds to an ellipse with different eccentricity,which describes the uncertainty area of the segment adaptively.A specialized similarity measure method considering uncertainty called UTSM based on the model is also proposed.Validated by experiments on both synthetic and real-world data,UTSM performs well in various evaluation indicators,i.e.,more robust to noise and outliers,more tolerant of different sample frequencies and asynchronous sampling of trajectories.It can effectively deal with the uneven data quality of trajectories,which is vital in fuzzy trajectory clustering,trajectory similar pattern mining,map matching,etc..(4)Subsegment similarity matching method based on multi-layer trajectory fragment coding tree.While it is hard tp grasp the granulate of trajectory sub-segment similarity matching and it is complex to traverse all granulate options,this thesis reconsider the timeordered serializability and continuous structure of the trajectory segment from a multigranularity perspective.Combined with proposed AHG method,a multi-layer structure of trajectory fragment coding tree is proposed.The code tree forms a hierarchical organizational form and sub-segment subordinate relationship expression from the entire trajectory to the smallest fragment at an acceptable time and space cost.A subsegment similarity matching method based on the trajectory code tree is designed afterwards,which realized the similarity analysis of different granularity of trajectories.It transforms the complex spatial calculations into geocode string's matching operations,which greatly reduced the computational complexity of the similarity matching of the subsegments.Without affecting matching accuracy,the efficiency is improved by more than an order of magnitude compared with the classical distance-based similarity measurement method.The method provides a new perspective for to multi-level trajectory pattern mining and analysis.