Spatial and spatio-temporal queries in the presence of uncertainty and movement

Over the past decade, spatial and spatio-temporal databases have found important applications in areas such as urban planning, geographical information systems (GIS), computer aided design (CAD) and NASA's earth observation systems. Much work exists on conventional spatial and spatio-temporal queries, but there has been growing interest in evaluating such queries in the presence of movement or uncertainty. First, advances in GPS technologies have created a variety of new applications, such as location-based services, vehicle fleet tracking, and E911 emergency service, which issue complex spatio-temporal queries on the trajectories of moving objects. Second, while it is typically assumed the positional attributes of spatial objects are precisely known, they may be known only approximately in practice, with uncertainty depending on the nature of the measurements and the source of data.; The presence of movement or uncertainty requires new techniques to evaluate spatial and spatio-temporal queries. First, unlike traditional spatial databases whose volume is relatively static, the volume of the trajectory data grows rapidly, requiring new and efficient indexing methods to ensure quick responses. Second, these new applications give rise to new types of queries, which are not supported in the traditional spatial databases. Finally, since uncertainty may affect the accuracy of the answer to queries, traditional techniques are inadequate to evaluate spatial data with uncertainty.; In this thesis, we present new efficient techniques to process spatial and spatio-temporal queries in the presence of uncertainty and movement. First, we present an efficient spatio-temporal index method based on polynomial approximation for search on trajectory data of moving objects. We show that our technique can process trajectories in both offline and online fashion, with performance superior to previous approaches. Second, we propose point-wise dense region queries, a new type of query, to identify regions with a high concentration of moving objects. We develop two efficient methods to exactly or approximately evaluate point-wise dense region queries. Finally, we propose the notion of probabilistic spatial query to handle uncertainty in spatial databases. We also present a new probabilistic index structure to evaluate probabilistic spatial queries efficiently.