Data management of moving objects

With the growing popularity of mobile computing devices and wireless communications, managing dynamically changing information about moving objects has become feasible. There are several applications that will benefit from data management for moving objects. The time-dependent shortest path problem in the context of transportation is one such application. In this dissertation, a moving object is modeled as a sizable physical entity equipped with a Global Positioning System, wireless communication capability, and a computer such as PDA. The main focus is on vehicles in a network of highways.; We have developed a model (the Space-Time Grid model) to efficiently manage dynamically changing information about moving objects in a one-dimensional space. In the Space-Time Grid model, the space-time domain is partitioned into a grid and the trajectory of a moving object is modeled as a polyline. The polyline is the result of interactions among other moving objects. The insertion and deletion algorithms and algorithms for processing range queries and k nearest neighbor queries in such an environment are presented. The range query algorithm is combined with an efficient filtering technique which determines if a polyline corresponding to the trajectory of a moving object intersects with a given range. A performance study of the system shows that despite the filtering step, for moderately large ranges, the proposed range query algorithm outperforms the algorithm without filtering.; The system is then extended to two-dimensional space to handle moving objects following certain paths in a network of routes. The system can be used to provide time-dependent shortest paths to moving objects. A performance study shows the benefit of our approach.