Database Reference
In-Depth Information
Record-id Location
Time
Sensor-id Speed Confidence
R
1
A
07/15/2001 00:01:51
S
101
60
0.3
R
2
B
07/15/2001 00:01:51
S
206
55
0.4
R
3
B
07/15/2001 00:01:51
S
231
47
0.5
R
4
A
07/15/2001 00:01:51
S
101
45
1.0
R
5
E
07/15/2001 00:01:51
S
063
52
0.8
R
6
E
07/15/2001 00:01:51
S
732
43
0.2
Generation rules:
R
2
⊕
R
3,
R
5
⊕
R
6
(a) Roadside sensor records.
Possible world
Probability Top-2 speeding records
W
1
=
{
R
1
,
R
2
,
R
4
,
R
5
}
0
.
096
R
1
,
R
2
W
2
=
{
R
1
,
R
2
,
R
4
,
R
6
}
0
.
024
R
1
,
R
2
W
3
=
{
R
1
,
R
3
,
R
4
,
R
5
}
0
.
12
R
1
,
R
5
W
4
=
{
R
1
,
R
3
,
R
4
,
R
6
}
0
.
03
R
1
,
R
3
W
5
=
{
R
1
,
R
4
,
R
5
}
0
.
024
R
1
,
R
5
W
6
=
{
R
1
,
R
4
,
R
6
}
0
.
006
R
1
,
R
4
W
7
=
{
R
2
,
R
4
,
R
5
}
0
.
224
R
2
,
R
5
W
8
=
{
R
2
,
R
4
,
R
6
}
0
.
056
R
2
,
R
4
W
9
=
{
R
3
,
R
4
,
R
5
}
0
.
28
R
5
,
R
3
W
10
=
{
R
3
,
R
4
,
R
6
}
0
.
07
R
3
,
R
4
W
11
=
{
R
4
,
R
5
}
0
.
056
R
5
,
R
4
R
6
(b) The possible worlds of Table 1.1(a).
Table 1.1
Speed records reported by sensors.
W
12
=
{
R
4
,
R
6
}
0
.
014
R
4
,
Scenario 3: Finding optimal paths in road networks with uncertain travel time.
The speed information recorded by sensors, together with the geographic infor-
mation, can be used to estimate the travel time along each road segment. However,
the estimated travel time derived from sensor readings is inherently uncertain and
probabilistic, due to the uncertain nature of the collected sensor data. Thus, a road
network can be modeled as a simple graph with probabilistic weights.
Suppose in an uncertain traffic network, from point A to point B there are two
paths, P
1
and P
2
. The set of travel time samples (in minutes) of P
1
is
{
,
,
,
}
35
35
38
40
and the set of samples of P
2
is
{
,
,
,
}
. Should each sample take a member-
ship probability of
25%
, the average travel time on both P
1
and P
2
is
37
minutes.
Which path is better?
On the one hand, if a user wants to make sure that the travel time is no more than
40
minutes, path P
1
is better since according to the samples, it has a probability of
100%
to meet the travel time constraint, while path P
2
has a probability of only
50%
to meet the constraint. On the other hand, if a user wants to go from A to B in
30
minutes, path P
2
should be recommended since the path has a probability of
50%
to
make it while P
1
has no chance to make it.
In Chapter 8, we will discuss the problem of path queries in probabilistic road
networks in detail.
25
25
48
50
