| Emerging location based applications (LBA) such as air traffic control, intelligent transportation system, digital battlefields and fleet management are maturing as the underlying technologies of wireless communication and GPS mature. Inherent to all such applications is the need to store, retrieve and manage information about the spatial and the temporal attributes of a large number of mobile entities.Typically, objects move along highly non-linear networks of roads, and distances between objects are frequently measured along the roads, and not as the Euclidean separations in R2 , as in most current work. Spatial queries admit efficient solution because data points lie on the plane and distances, which are Euclidean separations, are efficiently computed. Moreover, spatial databases can easily be partitioned while preserving proximity information. This property is the key to the success of spatial index structures such as R-trees and Quad-Trees.To make spatio-temporal queries as efficient as their spatial counterparts, we need to compute shortest distance quickly and allow for proximity-based partitioning.Current algorithms for shortest distance computation turn out not to have the properties that required for spatio-temporal queries. We first present a novel coding-based technique for answering spatial and spatiotemporal queries on objects moving along a system of curves on the plane, such as road networks. It handles join, range, intercept, and other spatial and spatiotemporal queries with distances being measured along the trajectories.This is an advance toward solving the problem in its more general form.Subsequently, we discuss algorithms that are applicable to shortest distance computation over general non-planar graphs. In particular for planar graphs, our DL algorithm computes shortest distances in O(log n) time using O( n n log n) space and O(1) disk access. Our second algorithm NDL reduces storage cost at the expense of distance computation performance. The data structure requires O(n n4 log n) space while the distance computation requires O( n4 log2 n) time and O( n4 ) disk accesses. |
