An Analytic Solution to the Alibi Query in the Space-time Prisms Model for Moving Object Data

International Journal of Geographical Information Science, Volume 25, Issue 2, 2011

Bart Kuijpers; Rafael Grimson; Walied Othman

“Moving objects produce trajectories, which are stored in databases by means of finite samples of time-stamped locations. When speed limitations in these sample points are also known, space-time prisms (also called beads) (Pfoser and Jensen 1999, Egenhofer 2003, Miller 2005) can be used to model the uncertainty about an object’s location in between sample points. In this setting, a query of particular interest that has been studied in the literature of geographic information systems (GIS) is the alibi query. This boolean query asks whether two moving objects could have physically met. This adds up to deciding whether the chains of space-time prisms (also called necklaces of beads) of these objects intersect. This problem can be reduced to deciding whether two space-time prisms intersect.

“The alibi query can be seen as a constraint database query. In the constraint database model, spatial and spatiotemporal data are stored by boolean combinations of polynomial equalities and inequalities over the real numbers. The relational calculus augmented with polynomial constraints is the standard first-order query language for constraint databases and the alibi query can be expressed in it. The evaluation of the alibi query in the constraint database model relies on the elimination of a block of three exªistential quantifiers. Implementations of general purpose elimination algorithms, such as those provided by QEPCAD, Redlog, and Mathematica, are, for practical purposes, too slow in answering the alibi query for two specific space-time prisms. These software packages completely fail to answer the alibi query in the parametric case (i.e., when it is formulated in terms of parameters representing the sample points and speed constraints).

A space-time prism and a lifeline necklace.

A space-time prism and a lifeline necklace.

“The main contribution of this article is an analytical solution to the parametric alibi query, which can be used to answer the alibi query on two specific space-time prisms in constant time (a matter of milliseconds in our implementation). It solves the alibi query for chains of space-time prisms in time proportional to the sum of the lengths of the chains. To back this claim up, we implemented our method in Mathematica alongside the traditional quantifier elimination method. The solutions we propose are based on the geometric argumentation and they illustrate the fact that some practical problems require creative solutions, where at least in theory, existing systems could provide a solution.”

A Class of Covariate-dependent Spatiotemporal Covariance Functions for the Analysis of Daily Ozone Concentration

The Annals of Applied Statistics, forthcoming article

Brian James Reich, Jo Eidsvik, Michele Guindani, Amy Nail, and Alexandra Schmidt

“In geostatistics, it is common to model spatially distributed phenomena through an underlying stationary and isotropic spatial process. However, these assumptions are often untenable in practice because of the influence of local effects in the correlation structure. Therefore, it has been of prolonged interest in the literature to provide flexible and effective ways to model non-stationarity in the spatial effects. Arguably, due to the local nature of the problem, we might envision that the correlation structure would be highly dependent on local characteristics of the domain of study, namely the latitude, longitude and altitude of the observation sites, as well as other locally defined covariate information. In this work, we provide a flexible and computationally feasible way for allowing the correlation structure of the underlying processes to depend on local covariate information. We discuss the properties of the induced covariance functions and methods to assess its dependence on local covariate information. The proposed method is used to analyze daily ozone in the southeast United States.”