Database Reference
In-Depth Information
R(X1,Y1)
S(X2,Y1)
.
a(2,0,1)
.
b(1,0,0)
T(X1,Y2)
U(X2,Y2)
Figure 5.6 Projection of a space-time prism for two points,
a
and
b
.
Definition 5.8. An object is moving along a finite system (or set) of streets,
N.
A location-aware device provides an estimate for the vehicle's location at a finite
number of points in tim
e,
denoted by
{
0
,
1
,...,t
}
.
The vehicle's actual location
at time
t
is denoted by
P
t
and the e
st
imate is denoted
P
t
.
Map matching
is the
process of determining the street in
N
that contains
P
t
. That is, to determine the
street that the vehicle is on at time
t.
For applying the space-time prisms method to the map-matching problem,
we must first make the following considerations. Given the time between two
consecutive recorded points,
a
and
b
, and a maximal speed, a car could have been
inmany possible locations, determined by the projection of the space-time prisms
over the plane. Even though this projection would be an ellipse, we can simplify
this computation defining a bounding box given by two points,
R
(
X
1
,Y
1
)and
U
(
X
2
,Y
2
), as Figure
5.6
shows (the line within the ellipse represents the actual
road).
R
is computed as follows:
X
1
is the farthest point on the
x
-axis that can
be reached moving away from
b
driving at maximum speed
v
max
.
Analogously,
Y
1
is the is the farthest point on the
y
-axis that can be reached moving away
from
b
driving at maximum speed
v
max
.U
is computed as follows:
X
2
is the
farthest point on the
x
-axis that can be reached moving away from
a
driving at
maximum speed
v
max
.
Analogously,
Y
2
is the is the farthest point on the
y
-axis
that can be reached moving away from
a
driving at maximum speed
v
max
.
We next sketch an algorithm for map matching based on space-time prisms
(in the following, ST-MM).
1. First, bound the network by calculating, for each pair of consecutive points,
the roads that connect them (as described above).
2. For each GPS point, compute the
n
closest road segments, assigning weights
to each segment in a way such that the one closest to the point gets weight
n
,
