Managing uncertainty in spatiotemporal databases

Applications that deal with large sets of Moving Objects (MOs) continue to grow, and so does the demand for an efficient data management and query processing systems supporting MOs. Application examples include location-based services, transportation management and mobile networks, which require an efficient database management system that is able to store, update, and query a large number of continuously changing MOs. Major challenges for developing such systems are due to the fact that the actual data object reports its state, which is associated with one or more properties (e.g., geographic location and velocity), that can continuously change over time, however, it is only possible to discretely record the object's states. All the missing or non-recorded states collectively form the uncertainty of the object's history. This dissertation reviews existing uncertainty models and proposes a more efficient model called the Tornado model that reduces the size of uncertainty regions resulting in less false hits, thus improving the efficiency of the database management system. The Tornado model resulted in an average reduction of 94% in the uncertainty volume over the Cone model---one of the most common uncertainty models in spatiotemporal databases.To be practically viable, each uncertainty model must be paired with appropriate approximations of uncertainty regions that can be used for indexing. This is due to the two-phase query processing system consisting of the refinement phase and the filtering phase. In this dissertation, we propose Minimum Bounding Rectangle (MBR) approximations for three uncertainty models including the Tornado model we also propose an estimated MBR for the Tornado model that achieves a good balance between accuracy and computation efficiency. The estimated MBR of the Tornado model reduced the number of false hits by 29% on average over the Cone model.Finally, this dissertation presents the Truncated Tornado model---an uncertainty model as a significant advance in minimizing uncertainty regions associated with MOs. This model achieves the reduction in uncertainty regions by removing sub-areas that are unreachable considering the maximum velocity and acceleration of the MOs. We combine the Truncated Tornado model with an approximation technique called Tilted Minimum Bounding Box (TMBB) to make the indexing of the uncertainty regions more efficient. Experimental results showed that the Truncated Tornado in TMBB resulted in an average volume reduction of 96% over the axis-parallel MBB of the Cone model.