An Efficient Indexing Mechanism Research Of The Position Of Moving Objects

With the arrival of 3G and the popularity of substantive wireless devices that have the locating function, a location-based service (LBS, for short) becomes possible. Accordingly, tracking moving objects in the corresponding position has become increasingly feasible and necessary, so we need some indexing structure that has high efficiency to locate the positions of moving objects. However, the traditional spatial-temporal indexing techniques for moving objects can not simultaneously and efficiently support the query about the past, present and future positions of moving objects, this is induced by the complexity of the spatial data and the dynamic attribute of the moving objects.The TEB~x (Time Entropy B~x) mixed indexing structure proposed in this paper, which being improved based on the B~x-tree indexing structure and adding the Hash auxiliary index-table to support the frequent update of moving objects , can efficiently solve the problem presented above. It simplifies the indexing keyword in order to increase the indexing temporal span, and expresses the positions of moving objects by using the linear function of time, so it can index the positions of moving objects from past to future; at the same time, the indexing structure introduces the time entropy for denoting the decreasing measurement of the positional information of moving objects in database as time increasing, so it can termly prune those positional information of moving objects which being stored beyond a definite period, and maintain the indexing structure on a steady size to improve the indexical efficiency of the system.The TEB~x-mixed indexing structure stores the positions of moving objects in a B~+-tree forest, it can efficiently support the query about the past, present and future positions of moving objects; it also supports the spatial-temporal rang query with the larger temporal span and the queries that select objects based on temporal and spatial constraints, such as queries that retrieve all objects whose positions fall within a spatial range during a set of time intervals at the same time; Compared with the B~x-tree indexing structure, because the Hash auxiliary index-table introduced by the TEB~x-mixed indexing structure can efficiently support the bottom-to-up partial update strategy, so it also has higher insertion, deletion and updating efficiency.