Solutions to the Generalised Alibi Query in Moving Object Databases

In Moving Object Databases (MODs), various data models and query languages have been proposed to deal with moving objects whose position is recorded by location-aware devices (such as GPS), at not always regular moments in time [2]. The movement data of an object is therefore discrete in nature and can be seen as a sequence $⟨(x_1,y_1,t_1),\mathrm{\dots },(x_n,y_n,t_n)⟩$ of measured space-time locations, which we call a trajectory sample. Between measured space-time points, the trajectory of a moving object is unspecified and unknown and several models have been proposed to deal with this uncertainty. Based on the assumption that moving objects have some physically determined or law imposed speed bounds, the space-time prism model delimits the region in space-time which a moving object may have visited between two sampled points. This model, originating from the field of “time geography” in the 1970s, has found its way into MOD research. The uncertainty on the movement of an object associated with a trajectory sample, is then modeled by a chain of space-time prisms. An illustration of two chains is shown in Figure 1.

One query of particular interest in this context is the alibi query, which asks whether two moving objects may have met, given their trajectory samples and speed bounds. The difficulty of answering this query can be reduced to deciding whether two space-time prisms intersect. Using a geometric argument, a solution to this problem was given by Othman et al. [5]. We address the generalised alibi query, which asks the same question, but for any (finite) number of moving objects. Because a space-time prism can be described by a system of polynomial inequalities, the generalised alibi query can be expressed as an existential first-order logic formula over the ordered field of real numbers. While there are algorithms for deciding the truth of such sentences [1], existing implementations cannot solve the query in practice (that is, within an acceptable amount of time). We provide several solutions (mainly via the spatial and temporal projection) to this query with varying time complexities. These algorithmic solutions rely on techniques from convex and semi-algebraic geometry, because space-time prisms are both convex and semi-algebraic sets. We also address variants of the generalised alibi query where the question is asked for a given spatial location or a given moment in time. Additionally, some of our methods are capable of producing a sample point, which is a point in the intersection of the $𝗇$ space-time prisms, if it exists. Finally, we give a quantifier-free description of the spatial projection of the intersection of $𝗇$ space-time prisms, which is exactly the region in space where the objects may have met (between two measured points), and allows answering the spatial variant of the generalised alibi query in linear time.

Our main contributions are summarised in Tables 1 and 2, which give an overview of the proposed methods or problems, their time complexity and their ability to produce sample points. For clarity, the complexity results in this table refer to deciding the emptiness of the intersection of $𝗇$ prisms. When the $𝗇$ moving objects are given by chains of prisms then the time complexity results in the table need to be multiplied by $L-𝗇+2$, where $L$ is the total number of prisms in the $𝗇$ chains.

We give a brief summary of the workings of each of the proposed methods in the next sections.

The essence of this method is to test whether the spatial projection of the intersection of the $𝗇$ space-time prisms is empty. Because this projection is precisely the region in space where the $𝗇$ objects could theoretically have met, we call it the meeting region. We show, using Fourier-Motzkin elimination, that the meeting region can be characterised as the intersection of regions enclosed by curves called “Cartesian ovals”, which are generalisations of ellipses. An illustration of the meeting period as the intersection of such regions is shown in part (b) of Figure 2. This characterisation has two uses. On one hand, it provides a linear-time solution to the generalised alibi query at a fixed location, which includes the production of sample points. On the other hand, we can use it to test the emptiness of the meeting region, providing an answer to the generalised alibi query. To do this, we make use of the algebraic nature of Cartesian ovals, which allows us to compute a (finite) set of “candidate points”, with the property that the meeting region is not empty if and only if it contains one of those candidate points. This method requires $O({𝗇}^5)$ time and also produces sample points.

Due to Helly’s theorem [3], which gives an equivalent condition for the non-emptiness of the intersection of convex sets, we can also solve the generalised alibi query by applying the above method to every combination of 4 of the $𝗇$ space-time prisms. The result of this is a method that only requires $O({𝗇}^4)$ time. However, the disadvantage of that method is that it cannot produce sample points.

The method described here works by testing the emptiness of the temporal projection of the intersection of the space-time prisms. This temporal projection is called the meeting period, as it is precisely the period of time during which the $𝗇$ moving objects could have met. Because space-time prisms are closed and convex sets, the meeting period is a closed interval. In fact, not only can we test its emptiness, we can explicitly compute the meeting period, that is, compute its minimum and maximum. To do this, we give a new characterisation of the meeting period, based on Helly’s theorem. This characterisation tells us that the computation of the meeting period can be reduced to the computation of the temporal projection of the intersection of three cones. An illustration of this characterisation of the meeting period is shown in part (c) of Figure 2. We have to compute such projection for every combination of three out of a set of $2𝗇$ cones. Because computing the temporal projection of three cones obviously takes constant time, the meeting period can be computed in $O({𝗇}^3)$ time.

To compute the temporal projection of the intersection of three cones, we show that the minimum and maximum of such interval are contained in a finite set of “candidate moments”. Then, we only have to test which of the candidate moments are contained in the temporal projection, which is straightforward.

Finally we use a general property about the intersection of convex sets to show that, given a moment in the meeting period, we can find a sample point in the intersection of the space-time prisms, also in $O({𝗇}^3)$ time.