Mobility and Uncertainty - Mobility Data - page 92

R3

R2

R1

(a) (b) (c)

Figure 5.2 Uncertain query operators: (a) Possibly Sometime Inside R1; (b)
Possibly Always Inside R2; (c) Always Possibly Sometime Inside
R3 (c). Dashed lines indicate PMCs that satisfy the predicates. Solid lines represent the
routes, and solid ellipses the uncertainty zones.

Figure 5.2 illustrates the semantics of the first three operators.

5.3.2 The Space-Time Prism Model

We now discuss the more general space-time prism model for uncertainty man-
agement, and describe its possible application to different problems. This model
assumes that besides the time-stamped locations of the object, also some back-
ground knowledge, in particular a (e.g., physically or law-imposed) speed limita-
tion v i at location ( x i ,y i ) is known. The speed limits that hold between two con-
secutive sample points can be used to model the uncertainty of a moving object's
location between sample points. The approach of Section 5.3.1 (sometimes
called the cylinder approach) depends on an uncertainty threshold value r> 0
which produces a sort of buffer along the trajectory. Instead, in the space-time
prism approach, for each consecutive pair of points ( t i ,x i ,y i ) , ( t i + 1 ,x i + 1 ,y i + 1 )
in a trajectory T , their related space-time prism does not depend on an uncer-
tainty threshold value, but rather on a maximal velocity value v max of the moving
object.
Intuitively, the space-time prism between two consecutive points is defined
as the set of time-space points where the moving objects may have passed,
respecting the speed limitation. The chain of space-time prisms connecting
consecutive trajectory points is denoted the lifeline necklace (see Figure 5.3 ).
We now formalize the concepts above. We know that at a time t , t i ≤ t ≤ t i + 1 ,
the object's distance to a point ( x i ,y i ) is at most v i ( t − t i ) and its distance to
( x i + 1 ,y i + 1 ) is at most v i ( t i + 1 − t ). The spatial location of the object is there-
fore somewhere in the intersection of the disc with center ( x i ,y i ) and radius
v i ( t − t i ) and the disc with center ( x i + 1 ,y i + 1 ) and radius v i ( t i + 1 − t ). The geo-
metric location of these points is referred to as a space-time prism , and defined
as follows, for general points p = ( t p ,x p ,y p )and q = ( t q ,x q ,y q ), and speed

limit v max .