Database Reference
In-Depth Information
Definition 5.5. Consider a road network
RN
, given by the tuple
(V,E)
and
to points
p
(
x
q
,y
q
)on
RN
, not necessarily vertices; the
point
p
lies on the embedding of the edge ((
x
p,
0
,y
p,
0
)
,
(
x
p,
1
,y
p,
1
)) and
q
lies on the embedding of the edge ((
x
q,
0
,y
q,
0
)
,
(
x
q,
1
,y
q,
1
)). We construct a
new
road network
RN
pq
from
RN
, such that
V
pq
=
V
∪{
p, q
}
,and
E
pq
=
E
∪
{
((
x
p,
0
,y
p,
0
)
,
(
x
p
,y
p
))
,
((
x
p
,y
p
)
,
(
x
p,
1
,y
p,
1
))
,
((
x
q,
0
,y
q,
0
)
,
(
x
q
,y
q
))
,
((
x
q
,y
q
)
,
(
x
q,
1
,y
q,
1
))
}
.
=
(
x
p
,y
p
)and
q
=
Definition
5.5
builds a new network by splitting the edges on which
p
and
q
are located. The speed limits are the ones of the original edges, and the time
spans of the new edges are computed according to Definition
5.4
. Based on
this construction, we define the distance along the road network
RN
and the
space-time prism between
p
and
q
on
RN
.
Definition 5.6. Let
RN
be a road network and let
p, q
∈
RN
.The
road network
time
between
p
and
q
, denoted by
d
RN
(
p, q
), is the shortest-path distance (i.e.,
as usual in graph theory) between
p
and
q
in the graph (
V
pq
,
E
pq
), with respect
to the time span labeling of the edges.
Note that the
road network time
between
p
and
q
in Definition
5.6
returns the
earliest possible time from
q
to
p
and vice versa. The metric takes two points
from a road network and returns the shortest time needed to get from one to the
other when traveling at the allowed maximal speed at each segment. If there are
different speed limits per edge, then the metric of Definition
5.6
is the shortest
time span metric on the temporal projection of the spatio-temporal data. In this
case the shortest paths are not always the fastest paths. Conversely, if all edges
in road network have the same speed limit, then the metric results in the shortest
path on the graph embedding.
We are ready to define
a space-time prism on a road network
. We provide a
simplified definition, and omit the most technical details.
Definition 5.7. A
space-time prism on a road network
between two spatio-
temporal points (
x
p
,y
p
,t
p
)and(
x
q
,y
q
,t
q
), is the geometric location in
R
×
RN
⊂
R
×
R
2
of all points a moving object could have visited when traveling,
restricted to
RN
, from an origin
p
to a destination
q
within a time frame ranging
from
t
p
to
t
q
, respecting the speed limits on the edges of
RN
. That means that
given a point
u
=
(
x,y
)
∈
RN
,
d
RN
(
p, u
)
+
d
RN
(
u, q
)
≤
(
t
q
−
t
p
).
Figure
5.5
shows an example of a space-time prism.
5.3.4 An Application: Using Space-Time Prisms for Map Matching
Chapter
2
studied a typical problem that presents in network-constrained trajec-
tories: map matching. Informally, this problem consists in mapping a trajectory
