Visit Probability in Space-Time Prisms for Moving Object Data

In a wide range of applications that deal with moving objects (such as people, animals or vehicles), time-stamped location data are collected using location-aware devices (such as GPS) and these data are stored and managed in moving object databases (MODs) [3]. The actual space-time trajectories of the moving object may be reconstructed or estimated from these measured space-time locations (called anchor points) using, for example, linear interpolation [11]. Space-time prisms, originating from the field of time geography [1, 4, 7], are used in Geographical Information Systems (GIS) [9] and MODs [2, 5] to model the movement uncertainty of a moving object between anchor points, based on a known speed bound on the object’s movement. For spatio-temporal anchor points $(p^{-},t^{-})$ and $(p^{+},t^{+})$, with , and a speed bound $v_{max}$, the prism with these and anchors and speed bound is denoted $𝒫(p^{-},t^{-},p^{+},t^{+},v_{max})$. Figure 1 depicts space-time prisms for movement in a two- and a one-dimensional space, respectively. As shown in the figure, prisms can be seen there to be the intersection of a future and past cone. The spatial projection of the prism, also called the potential path area, is an envelope of the spatial whereabouts of the moving object between the measured spatial locations.

In its basic form, a space-time prism lacks any internal structure and can be seen as a homogeneous geometric object, meaning that no two space-time points can be distinguished as more or less likely to have been visited. Conceptually, an infinite number of velocity-bound trajectories can be imagined within a prism and each point inside a prism is visited by infinitely many of them (except for some boundary points). This means that there is no a-priori reason to distinguish between space-time points inside the prism. Still, in many applications, such as animal or human movement [8], it is plausible that certain points in a prism, such as those on a linear interpolation path, should be considered more likely than other space-time points that are more towards the boundary of the prism (since they require a considerable detour). The notion of probability distributions in space-time prisms has become known as visit probability and has been studied extensively in the past decades (see e.g., [10, 12]). Several proposals have been made to assign probability values to space-time points or regions within a prism, thus providing the prism with an internal structure that expresses the unequal movement opportunities within the prism. Many of these proposals take an, often ad-hoc, approach towards the problem of establishing a visit probability for a particular application and each approach necessarily depends on a series of assumptions, which often remain obscure to a certain extend and the resulting visit probability therefore directly reflects these assumptions (in the best case, in a transparent way).

In this paper, we develop a general framework (or theory) of visit probability in the context of space-time prisms. In this approach, we start from the clear understanding that any definition of visit probability assumes a probability distribution on the possible velocity-bound trajectories within a prism. Once a probability space is defined on the set of trajectories (including a $\sigma$-algebra and a probability function), we can clearly determine for which parts of a space-time prims a visit probability can be derived. We also specify which conditions the $\sigma$-algebra on the set of trajectories must satisfy in order to be able to speak about a visit probability of certain classes of subsets of interest in the prism. Next, we address the question that asks on which subsets of a prism on which the derived visit probability is really a probability. We give a characterization of exactly those subsets of a prism for which this is the case. These sets are what we call “singleton-separators” and they are a wider class of subsets than just time slices of prisms. In the above mentioned literature, it is often the case that some notion of visit probability that has been defined is only considered on time slices of a prism. Our result shows that in fact it can be considered a probability on a wider class of subsets.

In this section, we investigate how we can define the notion of “visit probability” on space-time prisms, thus providing some internal structure to an otherwise homogeneous prisms. Let $𝒫=𝒫(p^{-},t^{-},p^{+},t^{+},v_{max})$ be a space-time prism with anchors $(p^{-},t^{-}),(p^{+},t^{+})$ and speed bound $v_{max}\ge 0$. A $v_{max}$-trajectory in the prism $𝒫$ is a (differentiable) mapping $\gamma$ from the time interval $[t^{-},t^{+}]$ to space, that connects the anchor points and whose velocity vector is bounded in size by $v_{max}$ at all time. The set of $v_{max}$-trajectories in the prism $𝒫$ is denoted by ${\mathrm{\Gamma }}_{𝒫}$. Space-time prisms are homogeneous in the sense that a-priori no higher likelihood can be assigned to a point $(p,t)$ in a space-time prism $𝒫=𝒫(p^{-},t^{-},p^{+},t^{+},v_{max})$ as compared to another point $(p^{\prime },t^{\prime })$ in $𝒫$. In general, the sets of $v_{max}$-trajectories passing through these points have the same cardinality (only points on the “rim” of a prism are exceptions [6]). Only by assigning a probability (or probability distribution) to the set of $v_{max}$-trajectories ${\mathrm{\Gamma }}_{𝒫}$, we are be able to indicate certain points or parts of a prism as more likely than others. To obtain such a probability space on ${\mathrm{\Gamma }}_{𝒫}$, we need to specify a $\sigma$-algebra $𝒢$ of subsets of ${\mathrm{\Gamma }}_{𝒫}$ and to define a probability function $P$ on this $\sigma$-algebra.

Once such a probability space $({\mathrm{\Gamma }}_{𝒫},𝒢,P)$ has been specified, we can start working towards specifying a “visit probability”: for a subset $A$ of $𝒫$, for which ${\mathrm{\Gamma }}_{𝒫}(A)$, which is the subset of $v_{max}$-trajectories that intersect $A$, belongs to $𝒢$, we define the visit probability of $A$ (relative to the given probability $P$ on ${\mathrm{\Gamma }}_{𝒫}$) as $P({\mathrm{\Gamma }}_{𝒫}(A))$ and we denote it by ${\mathrm{𝗏𝗉}}_P(A)$.

However, the fact that ${\mathrm{\Gamma }}_{𝒫}(A)$ belongs to the $\sigma$-algebra $𝒢$ is not guaranteed. Indeed, a $\sigma$-algebra $𝒢$ on $𝒫$ can range from very “poor” (or $𝒢=\{\mathrm{\varnothing },{\mathrm{\Gamma }}_{𝒫}\}$) to very “rich” (or $𝒢=2^{𝒫}$). In the former case, we can derive the visit probability of very few subsets of the prism, whereas in the latter case, we can derive it for all subsets. When we are interested in knowing the visit probability of a certain class $ℱ$ of subsets of the prism $𝒫$, we can only obtain this visit probability when for $F\in ℱ$, we have that ${\mathrm{\Gamma }}_{𝒫}(F)$ belongs to the $\sigma$-algebra $𝒢$.

We turn to a visit probability for parts of the potential path area (PPA) of a prism. The following definition of visit probability of a part $A$ of the the PPA reflects the idea that a moving object has visited $A$ if at some point in time it has visited $A$. For a subset $A$ of the PPA, we denote the cylindrical subset $(A\times ℝ)\cap 𝒫$ of $𝒫$ by ${\mathrm{𝖢𝗒𝗅}}_{𝒫}(A)$ and when ${\mathrm{\Gamma }}_{𝒫}({\mathrm{𝖢𝗒𝗅}}_{𝒫}(A))\in 𝒢$, we can define the probability of visiting the part $A$ of the the PPA as ${\mathrm{𝗏𝗉}}_P({\mathrm{𝖢𝗒𝗅}}_{𝒫}(A))$.

In this section, we determine in which circumstances the definition of visit probability on a prism, as given above, gives rise to a probability space within the prism. When we have a prism $𝒫=𝒫(p^{-},t^{-},p^{+},t^{+},v_{max})$ and consider the time slices ${𝒫}_{t_1}$ and ${𝒫}_{t_2}$ at two different moments , then we clearly have ${\mathrm{𝗏𝗉}}_P({𝒫}_{t_1})=1$ and ${\mathrm{𝗏𝗉}}_P({𝒫}_{t_2})=1$, since every $v_{max}$-trajectory must intersect a time slice (that is ${\mathrm{\Gamma }}_{𝒫}({𝒫}_{t_1})={\mathrm{\Gamma }}_{𝒫}({𝒫}_{t_2})={\mathrm{\Gamma }}_{𝒫}$). Since $t_1$ and $t_2$ are different, we have that the time slices ${𝒫}_{t_1}$ and ${𝒫}_{t_2}$ are disjoint subsets of $𝒫$. For disjoint unions, we would expect ${\mathrm{𝗏𝗉}}_P({𝒫}_{t_1}\cup {𝒫}_{t_2})$ to be ${\mathrm{𝗏𝗉}}_P({𝒫}_{t_1})+{\mathrm{𝗏𝗉}}_P({𝒫}_{t_2})$, but since this is $1+1=2$, that cannot be the case. This simple example shows that ${\mathrm{𝗏𝗉}}_P$ is not a probability on the complete prism $𝒫$. This raises the question: are there subsets of a prism on which the visit probability of Section 2 is a probability? The main contribution of this paper is a characterisation exactly those subsets of a prism for which this is the case. These subsets are “singleton-separators” in a prims, which are illustrated in Figure 2 for one-dimensional movement. A subset $S$ of $𝒫$ is called a singleton-separator, if for any $v_{max}$-trajectory $\widehat{\gamma }\in {\mathrm{\Gamma }}_{𝒫}$, we have that the cardinality of $\widehat{\gamma }\cap S$ equals one.

For a subset $S$ of $𝒫$, we define $M_{𝒢}(S):=\{A\subseteq S\mid {\mathrm{\Gamma }}_{𝒫}(A)\in 𝒢\}$ and we have as a first result that $S$ is a singleton-separator if and only if for every $\sigma$-algebra $𝒢$ on ${\mathrm{\Gamma }}_{𝒫}$ we have that $M_{𝒢}(S)$ is a $\sigma$-algebra on $S$.

This means that the only subsets of a prism for which we can hope to obtain a probability space are the singleton-separators. The following theorem states how this probability space looks like.