Database Reference
In-Depth Information
set of vertices. An HP-tree can be constructed top-down starting from the root which
represents the complete set of vertices in graph
G
. Then, the graph is partitioned
recursively. For a non-leaf node
N
and the set of vertices
V
N
associated with
N
,an
m
-partitioning is applied to
V
N
and results in
m
exclusive subsets of
V
N
, namely
V
N
1
,...,
V
N
m
. Thus,
m
corresponding child nodes of
N
are constructed for
N
. The
partition continues until each subset contains at most
d
vertices (
d
is a user specified
number). Figure 8.7(b) shows a 2-nary HP-tree corresponding to the partition in
Figure 8.7(a). If we apply a linear time heuristic graph partitioning method [193],
then constructing an HP-tree using
m
-partitioning requires
O
n
log
m
d
)
(
time.
8.3.2 Approximating Min-Value Estimates
To approximate a min-value estimate, we store auxiliary information for each node
in an HP-tree as follows. For each leaf node
N
L
representing a vertex
v
and its parent
node
N
associated with a set of vertices
V
N
, we compute the weight of the shortest
path between
v
and each border vertex of
V
N
. The smallest weight is stored in
N
L
.
Then, for node
N
and each of its ancestor nodes
N
A
, let
V
A
be the set of vertices
associated with
N
A
. We compute the shortest paths between each border vertex of
V
N
and each border vertex of
V
A
. The smallest weight is stored in
N
.
For example, in the HP-tree shown in Figure 8.7(b),
F
is a leaf node, and we store
the smallest weight of shortest paths from
F
to the border vertices of
N
7, which is
w
1
in Figure 8.7(a). Then, for node
N
7, we compute the smallest weight of the shortest
paths between any border vertex in
N
7 and any border vertex in
N
3. Since
N
7 and
N
3 share a common border vertex (
I
), the smallest weight is 0. The smallest weight
of the shortest paths between
N
7 and
N
1is
w
2
in Figure 8.7(a).
The min-value estimate for a vertex
u
can be approximated as follows. Let
N
u
and
N
v
be the parent node of
u
and
v
, respectively. Let
N
be the lowest common
ancestor node of
N
u
and
N
v
. Then, the weight of any path between
u
and
v
is at
least
w
(
u
,
N
u
)+
(
,
)+
(
,
)+
(
,
)
(
,
)
(
,
)
w
N
u
N
w
v
N
v
w
N
v
N
, where
w
u
N
u
and
w
v
N
v
are the
smallest weight from
u
and
v
to
N
u
and
N
v
, respectively, and
w
)
are the smallest weight from
N
u
and
N
v
to
N
, respectively. Searching the lowest
common ancestor node of two vertices takes
O
(
N
u
,
N
)
and
w
(
N
v
,
N
log
m
d
)
time.
For example, in Figure 8.7, the lowest common ancestor node of
F
and
G
is the
root node, which is partitioned by
l
1
. Thus, the weight of the shortest path between
F
and
G
is at least
w
1
+
(
w
2
+
w
3
+
w
4
. It can be used as the min-value estimate of
F
with respect to the end vertex
G
.
8.3.3 Approximating Stochastic Estimates
To approximate a stochastic estimate, we store two pieces of information for each
node in the HP-tree.
