Database Reference
In-Depth Information
10
160
Exact
Sampling
approximation
Exact
Sampling
Approximation
8
140
120
6
100
80
4
60
40
2
20
0
0
5
10
15
20
25
30
0.1
0.3
0.5
0.7
0.9
Probability threshold
Weight threshold (%)
(a) Runtime vs.
l
.
(b) Runtime vs. probability threshold.
10
160
Exact
Sampling
Approximation
Exact
Sampling
Approximation
140
8
120
100
6
80
4
60
40
2
20
0
0
1
2
3
4
5
5
10
15
20
25
Variance
Number of samples of an edge
(c) Runtime vs. variance.
(d) Runtime vs. sample size.
Fig. 8.8
Efficiency of weight probability calculation methods.
250
100
DFS
P*+constant
P*+min-value
P*+stochastic
DFS
P*+constant
P*+min-value
P*+stochastic
200
80
150
60
100
40
50
20
0
0
30
40
50
60
70
0.1
0.3
0.5
0.7
0.9
Probability threshold
Weight threshold (%)
(a) Runtime vs.
l
.
(b) Runtime vs. probability threshold.
20
25
DFS
P*+constant
P*+min-value
P*+stochastic
DFS
P*+constant
P*+min-value
P*+stochastic
20
15
15
10
10
5
5
0
0
1
2
3
4
5
5
10
15
20
25
Variance
Number of samples of an edge
(c) Runtime vs. variance.
(d) Runtime vs. sample size.
Fig. 8.9
Efficiency of path search methods.
8.4.1 Simulation Setup
We test the efficiency, the memory usage, the approximation quality, and the scal-
ability of the algorithms o
n the following five real road network data sets
3
: City of
3
http://www.cs.fsu.edu/
˜
lifeifei/SpatialDataset.htm
