Database Reference
In-Depth Information
As discussed in Section 2.1.1, the distribution of
w
e
is often unavailable and can
be estimated by a set of
samples
{
x
1
,···,
x
m
}
, where each sample
x
i
>
0(1
≤
i
≤
m
)
m
i
=
1
Pr
takes a
membership probability Pr
(
x
i
)
∈
(
0
,
1
]
to appear. Moreover,
∑
(
x
i
)=
1.
2.3.3.1 Paths and Weight Distribution
A
simple path
P
is a sequence of non-repeated vertices
,...,
=
v
1
v
n
+
1
, where
e
i
(
n
).
v
1
and
v
n
+
1
are called the
start vertex
and
the
end vertex
of
P
, respectively. For the sake of simplicity, we call a simple path a
path
in the rest of the paper. Given two vertices
u
and
v
, the complete set of paths
between
u
and
v
is denoted by
v
i
,
)
≤
≤
v
i
+
1
is an edge in
E
(1
i
P
u
,
v
.
and
P
=
For paths
P
=
v
1
,...,
v
n
+
1
v
i
0
,
v
i
0
+
1
,...,
v
i
0
+
k
such that 1
≤
i
0
≤
k
,
P
is called a
super path
of
P
and
P
is called a
subpath
of
P
.
Moreover,
P
n
+
1
−
=
P
1
,
P
2
,...,
P
m
if
P
1
=
v
1
,...,
v
i
1
,
P
2
=
v
i
1
+
1
,...,
v
i
2
, ...,
P
m
=
v
i
m
−
1
+
1
,...,
v
n
+
1
,1
<
i
1
<
i
2
<···<
i
m
−
1
≤
n
.
P
j
(
1
≤
j
≤
m
)
is called a
segment
of
P
.
The
weight
of path
P
=
v
1
,...,
v
n
+
1
is the sum of the weights of all edges in
P
,
i
that is
w
P
=
∑
1
w
e
i
, where
w
e
i
is the weight of edge
e
i
=(
v
i
,
v
i
+
1
)
with probability
=
mass function
f
e
i
(
. Since each
w
e
i
is a discrete random variable,
w
P
is also a
discrete random variable. A
sample
of
P
is
x
P
=
∑
x
)
n
i
1
x
i
, where
x
i
(
1
≤
i
≤
n
)
is a
=
sample of edge
e
i
=(
v
i
,
v
i
+
1
)
. We also write
x
P
=
x
1
,...,
x
n
where
x
1
,...,
x
n
are
called the
components
of
x
P
.
The
probability mass function
of
w
P
is
∑
x
1
+
...
+
x
n
=
x
f
P
(
x
)=
Pr
[
w
P
=
x
]=
Pr
[
w
e
1
=
x
1
,...,
w
e
n
=
x
n
]
(2.5)
In road networks, the travel time on a road segment
e
may be affected by the
travel time on other roads connecting with
e
. Therefore, the weights of adjacent
edges in
E
may be correlated. Among all edges in path
P
, the correlation between
the weights
w
e
i
can be repre-
sented using different methods, depending on the types of correlations. To keep our
discussion general, in this paper we represent the correlations between
w
e
i
and
w
e
i
+
1
of two adjacent edges
e
i
and
e
i
+
1
(
1
≤
i
≤
n
)
and
w
e
i
+
1
using the joint distribution over the sample pairs
(
x
i
,
x
i
+
1
)
∈
w
e
i
×
w
e
i
+
1
. The
joint
probability mass function
1
of
w
e
i
and
w
e
i
+
1
is
f
e
i
,
e
i
+
1
(
x
i
,
x
i
+
1
)=
f
e
i
+
1
,
e
i
(
x
i
+
1
,
x
i
)=
Pr
[
w
e
i
=
x
i
,
w
e
i
+
1
=
x
i
+
1
]
.
Correspondingly, the
conditional probability
of
w
e
i
f
e
i
,
e
i
+
1
(
x
i
,
x
i
+
1
)
f
e
i
+
1
(
given
w
e
i
+
1
is
f
e
i
|
e
i
+
1
(
x
i
|
x
i
+
1
)=
.
x
i
+
1
)
Theorem 2.1 (Path weight mass function).
The probability mass function of a sim-
ple path P
=
v
1
,...,
v
n
+
1
(e
i
=(
v
i
,
v
i
+
1
)
for
1
≤
i
≤
n) is
1
The joint travel time distribution among connected roads can be obtained from roadside sensors.
The sensors report the speeds of vehicles passing the sensors. The speeds can be transformed into
travel time. A set of travel time values reported by sensors at the same time is a sample of the joint
travel time distribution.
