Research On Spatio-Temporal Indexing Mechanism And Querying Strategy

The researching of indexing and querying moving spatial objects is very important in spatio-temporal database, and valuable in applications of traffic control, navigating, land planning and mobile communication, it is a new issue in database researching domain. Since spatial data is multi-dimensional, while time dimension is for some extent different with spatial dimension, traditional methods of index and query are not applicable in such domain. Most of previous spatio-temporal indexes come from spatial indexes, which are called indexes of the R-tree family. With these indexes, the window-query, nearest neighbor-query, closest pair-query and other spatial queries evolve into queries with temporal constrains such as time slice, time interval and future time. Now, with the development of mobile applications, the issues of frequent updates on moving spatial object dataset, multiple spatio-temporal queries and continuous spatial queries become remarkable, which challenge previous methods of spatio-temporal index and query. To make the spatio-temporal database more applicable, it is necessary to solve these issues.Previous spatio-temporal indexes of the R-tree family focus on the refinement of structure and query performance, try to achieve low query cost with complex inserting algorithms, while the cost of updating is for some extent neglected. Basing on the fact that R-tree's nodes distribution is relevant with the distribution of spatial objects, which is relatively stable in moving object dataset, we introduce a batch-processing method with caches of operations and grid-partitioning of data space for R-tree updating. Seed nodes representing the distribution of objects are chosen by grid cells, a merging algorithm with seed nodes and grouping algorithm with seed records are designed for batch-processing. This method reduces the I/O cost of R-tree updating without violating the rules of R-tree node constructing, so, the query performance is not affected.An index structure for trajectories needs to deal with updating of objects'current position and preserve their historical spatial information, since the trajectory may need to be preserved continuously, early spatio-temporal indexes using version-splitting method do not suit for it. Previous trajectory indexes increase the trajectories'continuity while weaken the performance of spatial queries, and they also neglect the cost of updating. To solve these problems, a new trajectory indexing method is promoted, which mainly consider the moving distance of objects. By defining the trajectory unit, the index partitions trajectories reasonably, and the cost of maintenance is reduced. The experiment results show that such trajectory index using trajectory unit can support window query with time slice and interval constrains effectively, it reduces the number of index nodes, and optimizes the updating with a bottom-up inserting method.The TPR-tree is a variant of R-tree for spatio-temporal prediction queries, and is used in the TPNN algorithm, which outperforms earlier nearest neighbor predictive algorithms. The TPNN algorithm uses nearest neighbor query method on time parameters repeatedly, and check the objects every time they become candidate, thus increases the query's cost. To solve this problem, a new algorithm basing on distance functions is promoted. It constructs the objects'distance functions by traversing the index just once, and then, result of query is computed by sorting and analyzing these distance functions. The new algorithm avoids both traversing the TPR-tree and checking an object multiply, reduces the query's cost while consuming a certain quantity of main memory buffer.In dynamic environment of moving objects, a query point's location may also change, the strategy of multiple continuous spatial queries should be different with previous spatial time slice or time interval query algorithms basing on relative indexes. Among previous methods, the SEA-CNN algorithm is the most outstanding one, it reduces the I/O cost by maintaining the queries'influence and searching regions dynamically, and also by indexing the queries. However, the SEA-CNN method does not make full use of temporary results, and moving queries are not optimized fully. So, a dual cache strategy is promoted to reduce the times of re-computing static queries and further reduce moving queries'searching regions. The dual cache strategy achieves sharing among queries both on data accessing and temporary results, it has better system performance in the experiments, which is obvious when the objects'distribution changes slowly.Basing on the above-mentioned idea of using temporary results, the continuous group-nearest neighbor query can also be optimized, even on the CPU cost. By defining a query's containing-influence region, grid-cell-influence region and extended containing-influence region, the result list of query's initialization is extended reasonably, which does not increase the cost of initializing the queries obviously. Such strategy optimize the continuous group-nearest neighbor query by reducing the times of reinitializing and controlling the cost of initializing.Previous algorithms basing on MinMinDist values between R-tree nodes for closest pair query will become inefficient when the two joining datasets'area highly overlap, because they may get a long priority queue and visit one node multiply. To solve the problem in highly overlapping situation, a new method is presented, which converts the join operation into sub-queries inside a moving window. By defining the safe and exception area of a sub-window, together with the safe manner of sub-windows'distribution, the new method reduces the multiple accessing of R-tree nodes, and the I/O cost is decomposed into those of window-query in sub-windows.