Research And Implementation Of Indexing Techniques Of Spatio-temporal Database

The spatio-temporal database has received considerable attention in database techniques, due to the emergence of numerous applications (eg., traffic control systems, weather forecast, etc.). Spatio-temporal database combines temporal data with spatial data of spatio-temporal objects and handle those data efficiently. The index method is the key technique to support fastly accessing spatio-temporal data.According to the type of spaio-temporal data, index methods of spatio-temporal database generally fall into three categories: index for historical spatio-temporal data, index for current position and index for future position. R-tree has many variances which support different spatio-temporal queries in different organized methods for spatical data and temporal data. Contrail is a prototype system of spatio-temporal database which manages historical spatio-temporal data.A hybrid indexing structure named DPTI (Dynamic Packing Trajectory Index) is composed of R-tree and link-list. DPTI achievses trajectory preservation by using link-list and adopts a more reasonable algorithm to partition a trajectory into several subsections to decrease dead space of trajectory MBR. Then, the leafnode's entry of DPTI isn't pointing to a line segment, but a set of line segment.DPTI has a new update policy of trajectory and then forecasts the increase of entry which caused by trajectory update. Based on the forecast, a method named dynamic packing policy can pack the nodes which save historical data step by step while the trajectory dataset is very large.DPTI is a two-level index structure and guarantees strict trajectory preservation. The method of partition keeps neighboring line segments to be clustered in nodes. Dynamic packing policy enhances the storage utilization of index. Therefore the spatio-temporal queries of DPTI are improved efficiently.