Universal trajectory queries for moving object databases

In this paper, we consider a data model for uncertain trajectories of moving objects. In our model, the trajectory is a vector of uniform stochastic processes. We study "universal range queries" which examine whether the spatial properties of being inside a region hold throughout an entire time interval. An example of universal range queries is: "Retrieve all trucks staying in Santa Barbara area from 17:00 to 18:00 today". The main technical contributions are efficient algorithms for computing probabilistic answers to universal range queries. We show that the algorithms are efficient using theoretical worst case analysis and empirical studies. Interestingly, the practical complexity is better than theoretical bounds.