Representing And Indexing Trajectories For Efficient Similarity Search With TRI Framework

Queries on spatio-temporal trajectories have been studied for decades.However,how to measure the similarity of trajectories,and how to efficiently represent and index trajectories are still problems.For the first problem,we discuss the property of interpolation invariance and propose two distances with this property.For the second problem,we present our Trajectory Representing and Indexing(TRI)framework to manage the spatio-temporal trajectories.In this framework,firstly,trajectories are split into sub-trajectories according to our cost estimation and by the Orient-preserving Trajectory Splitting method.Secondly,sub-trajectories are represented by our new bounding box representation called Minimum Bounding Crystal.Thirdly,trajectory points and bounding boxes are indexed by our Trajectory-bundled 3DRTree.In the end,when handling the k nearest neighbor query,our new querysimplified sub-bounding-box-driven k nearest neighbor algorithm would be applied.Using experimental comparisons,we illustrate that the TRI framework could boost the efficiency of k nearest neighbor search by one magnitude.