Research On The Index And Queries Of Moving Objects

Moving object database technology is one of the emerging research areas which developed in recent years. The goal of the research on the technology is to figure out how to store the location data and other information of the moving objects in the database and execute the related query operations. Moving object database technology has a wide application prospect in moving computing, global positioning, transportation, geographic information system, military science and other fields. The indexing technology of moving objects is one of the core technologies which are closely related to the efficiency of the moving object database. And it has important research significances.So far, a lot of index structures for the moving object data have been proposed. The TPR-tree is one of the most attentioned index structures for moving object data. However there may be overlap between the middle nodes of the TPR-tree, which can lead to multiple queries. The purpose of this paper is to overcome the shortcomings of the TPR-tree multiple queries to improve the query efficency.Firstly, based on the structure of the TPR-tree and the idea of the MOIS-tree, we present a new moving object index structure the-OTPR-tree. OTPR-tree used a CTPBR(conservative time parameter bound rectangle) to approximate the moving object in space, and sorted the storage node in the tree according to the coordinate values of the two endpoints of the CTPBR diagonal, which can speed up the pruning efficency in the query operations.Secondly, according to the definition of the OTPR-tree, we present the pseudo code of the OTPR-tree construction algorithm, node insert algorithm and range query algorithm. We also prove that the algorithms are correct and terminable. The time complexity of the algorithms is presented and proved. Finally, through the research of the nearest neighbor queries based on OTPR-tree, we present the pseudo code of the OTPR-tree nearest neighbor query algorithm,&NN query algorithm and CNN(continuous nearest neighbor) query algorithm. Meanwhile, we present the time complexity proving, terminability proving and correctness proving of the algorithms.