Database Reference
In-Depth Information
l
1
l
1
G
F
C
w1
Border
vertices
{C,D,E}
F
A
w3
D
I
l
3
Border
vertices
{A,B}
l
2
w2
B
E
H
H
(a) A partition on a graph.
(b) A graph partition.
Fig. 8.6
A partition of a graph.
Using the stochastic estimates, in each step, the search algorithm visits the vertex
v
i
whose heuristic evaluation function using optimal virtual path
P
opt
is the largest.
However, constructing
P
opt
requires enumerating all possible paths from
v
i
to
v
,
which is computationally challenging. Therefore, in the next section, we discuss
how to approximate
P
opt
using a hierarchical partition tree index in real road net-
works.
8.3 A Hierarchical Index for P*
In this section, we introduce a hierarchical partition tree to index the vertices of a
graph and maintain the information of weight probability distribution for efficient
query answering using the P* algorithm.
8.3.1 HP-Tree Index
A graph partitioning divides the vertices of a graph into subsets of about equal size,
such that there are few edges between subsets [192]. Figure 8.6(a) illustrates a 2-
partitioning on a graph, where all vertices are divided into two subsets, separated by
l
1
. Among the vertices on the left of
l
1
, only
A
and
B
are connected to the vertices
on the right subset. Therefore, they are called
border vertices
. Similarly,
C
,
D
and
E
are the border vertices in the right subset.
The 2-partitioning can be applied recursively on each subset. As shown in Fig-
ure 8.6(a), the left subset is further partitioned into two smaller subsets by line
l
2
,
and the right subset is further partitioned into two smaller subsets by
l
3
. By recursive
partitioning, we can obtain a
hierarchical partition tree
of the graph, as illustrated
in Figure 8.7.
Given a graph
G
and an
m
-partitioning
P
on
G
,a
hierarchical partition tree
(HP-tree for short) is an
m
-nary tree that indexes the vertices in
G
according to
P
.
Each leaf node in an HP-tree represents a vertex, and each non-leaf node represents a
