Database Reference
In-Depth Information
7
50
Exact+DFS
Sampling+DFS
Approximation+P*
Approximation+P*
Exact+DFS
Sampling+DFS
6
40
5
30
4
3
20
2
10
1
0
0
5
10
15
20
25
30
0.2
0.4
0.6
0.8
Weight threshold (%)
Probability threshold
(a) Memory vs.
l
.
(b) Memory vs. probability threshold.
Fig. 8.10
Memory usage.
5
10
l=5%
l=10%
l=25%
l=5%
l=10%
l=25%
4
8
3
6
2
4
1
2
0
0
100
200
300
400
500
10
20
30
40
50
Number of samples
Bucket parameter t
(a) The sampling algorithm.
(b) The bucket approximation method.
Fig. 8.11
Approximation quality.
,
,
Oldenburg Road Network (
OL
)(6
104 nodes and 7
034 edges), City of San Joaquin
County Road Network (
TG
)(18
,
262 nodes and 23
,
873 edges), California Road
Network (
CAL
)(21
,
047 nodes and 21
,
692 edges), San Francisco Road Network
(
SF
) (174
,
955 nodes and 223
,
000 edges), and North America Road Network (
NA
)
(175
178 edges).
The available weight of each edge in the above real road networks is certain. To
simulate an uncertain road network, we generate a set of uncertain samples for each
edge following the Normal distribution and the Gamma distribution.
In the Normal distribution
N
,
812 nodes and 179
,
(μ
,
σ )
,
μ
is the original edge weight in the certain
graphs and
σ
is the variance.
σ
is generated for different edges following the Normal
distribution
N
(μ
σ
,
σ
σ
)
, where
μ
σ
=
xR
(
x
=
1% to 5%
)
and
R
is the range of weights
in the data sets. By default,
R
. This simulation method follows the
findings in the existing studies on traffic simulations [194], which indicates that the
travel time on paths in road networks follows the Normal distribution in short time
intervals.
To simulate the travel time in real road networks using the Gamma distribution
μ
σ
is set to 1%
·
=
θ
Γ (
is the origi-
nal edge weight in the certain graphs. Since the experimental results on the weights
under the Gamma distribution and the Normal distribution are highly similar, limited
by space, we only report the results on the data sets with the Normal distribution.
k
,
θ )
, as suggested in [195], we can set
θ =
0
.
16 and
k
, where
μ
