Application Research Of TPR-Tree For Location-based Service System

Spatio-Temporal Database (STDB) is a new field in computer science. Facing with large numbers of data, fast and efficiently indexing moving objects in certain spatial and temporal extent are a crucial issue in several application domains, such as LBS, Intelligence Transportation and Digital Battle. Spatio-Temporal index is the vital technique for solution of above problems.Spatio-temporal index methods focus on two orthogonal directions: (1) Indexing the past, (2) Indexing the current and predicted future positions. There are more concerns about latter one because of its functions in practical applications. The TPR-tree is a typical Spatio-temporal index technique that supports the efficient querying of the current and projected future positions of moving objects. The TPR-tree's basic algorithm is the same as that of the R*-tree, with one exception: instead of MBR, TPBR(Time-Parameterized Bounding Rectangle) are used.In this paper, we first review the STDB indices that have been researched. Specially, we focus on the three most important indices, i.e., R*-tree and TPR-Tree. We will concentrate on their basic structures and algorithms, as well as their advantages and disadvantages.By analyzing the structure and algorithms of TPR-tree, a LBS(Location-Based Service) system Support Predictive Query is designed. Then, paper also makes some improvement to the structure of TPR-tree. Specially, afterward we discuss and analyze the performance of the improved TPR-tree. The experimental comparison pointed out that the complexity of improved node-split algorithm is only 12-20% of primary node-split algorithm of TPR-tree, and the TPR-tree used improved node-split algorithm whose query performance is up to 50% better than the primary TPR-tree. Furthermore, the query performance of TPR-tree used distance-based structure adjusting policy also can increase by 10% or so solely.