Indexing And Querying Spatio-Temporal Trajectories With Semantic Labels

With the proliferation of GPS technology and intelligent terminals,a large number of spatiotemporal trajectories generate,that is time-varying position data.On the one hand,the traditional spatiotemporal trajectory does not consider the semantic information,can not fully depict moving object.On the other hand,existing semantic attributes correspond to the instant,can not reflect the semantics of the trajectory during time interval.A new model and index are introduced according to spatio-temporal trajectories with semantic labels,and corresponding query algorithms are proposed,which can be applied to many different scenarios such as route planning,friend recommendation system and trajectory pattern analysis.The main research work is as follows:(1)Semantic attributes are mapped to time instant in most existing spatio-temporal trajectories that contain semantic attributes,ignoring descriptions over time interval.To sovle this problem,spatiotemporal label trajectory model is introduced,which contains both semantic information mapped to interval and spatio-temporal attributes.In addition,LR-Tree is proposed,which is able to represent the semantic existence during time interval,LR-Tree contains the label layer and the spatial bitmap layer,and LR-Tree bulkload construction method is developed.The conducted experiment demonstrates the efficiency of bulkload method,and the semantic attributes account for the proportion of the overall disk space at 4%-7%.(2)Pattern match queries are introduced according to semantic descriptions of spatio-temporal label trajectory.Combined with traditional moving object queries,range pattern match query and k nearest neighbor pattern match query are introduced with formal representations.Range pattern match query algorithm and k nearest neighbor pattern match query algorithm based on LR-Tree are put forward,and this paper analyzes the filter and refine progress in the two algorithms.Through extensive experiments with different parameters of the query algorithm and compare with the existing indexes of moving objects,verifying the efficiency of the proposed algorithms.(3)Existing moving object query with semantic attributes further consider the space-time attributes under the premise of semantic matching,which leads to poor performance over spatial and temporal dimensions in some results.Motivated by this,partial pattern match query is developed with formal representations of revelant definition.Based on this,k nearest neighbor approximate pattern match query is introduced which put the spatio-temporal distance and semantic matching degree in the same priority,and corresponding algorithm based on LR-Tree is presented.Experiment results show that k nearest neighbor approximate pattern match query based on LR-Tree showing better pruning ability contrasting with query algorithms based on existing indexes under different parameters.