Information Technology Reference
In-Depth Information
10.3.2
Graph Segmentation Method and Strategy
Various ways how to assign the vertices to segments have been identified and
studied. One of them was a graph to forest of trees transformation which's result
is a forest of trees and was proposed in [7]. Combination of vertex clustering
and the graph to forest of trees transformation together with its preliminary
evaluation can be found in [8]. Further implementation and evaluation showed
that the graph to forest of trees makes the resulting indexing structure very
tangled and therefore the search algorithm did not present good results.
Therefore, for the experimental evaluation presented in this chapter we have
chosen the vertex clustering as a segmentation method. Initially it puts a single
vertex into set
V
S
. Afterwards it incrementally enlarges the segment with vertices
to which or from leads an edge to this vertex. Those edges then form the set
E
S
.
This continues until a maximal number of vertices in
V
S
is reached. For each
level the maximal number of vertices in
V
S
is stated as a parameter.
The nature of the
ρ
-index tree structure is very dependent on the settings
for the maximal number of vertices in
V
S
at each level. Intuitively, by setting
small sizes of the segments a slim and high tree can be created. On the other
hand, using a large number at first level a wide and low tree is acquired. The
evaluation of different parameter settings and how they affect the search itself
is demonstrated in Section 10.5.
10.3.3
Sequence of Segments Properties
As we mentioned above, each path on a lower level can be represented by some
segment sequence on the upper level. Intuitively, some two different paths can be
represented by one segment sequence. Some of those path are called
connecting
paths
and are defined in Definition 4. The main property of a connecting path
is that it starts with an common edge of first two segments and ends with a
common edge of last two segments in the sequence of segments.
Definition 4.
Connecting path in a sequence of segments:
Common edges CE
i
for
(
S
1
...S
l
)
:
1
≤
i
≤
l
−
1:
CE
i
=
EDGES OUT
(
S
i
)
∩
EDGES IN
(
S
i
+1
)
Connecting path
p =
(
e
1
e
2
...e
n
)
∈
(
S
1
...S
l
):
e
1
∈
CE
1
∧
e
n
∈
CE
l−
1
∧∃
i
2
,i
3
,...i
l−
1
:1
<i
2
<i
3
< ... < i
l−
1
<n
:
{
e
2
,...e
i
2
}⊆
E
S
2
∧{
e
i
2
,...e
i
3
}⊆
E
S
3
∧
...
∧{
e
i
l−
2
,...e
i
l−
1
}⊆
E
S
l−
1
In general, each segment sequence can represent a huge amount of paths of
different lengths. This is because each segment represents a subgraph in which
paths with different lengths can be found. Important to us is knowledge of a
length of the shortest path that the particular segment sequence represents.
Obviously, the shortest path is one of the connecting paths. The length of the
shortest path is then referred to as a
weight
of the sequence of segments. We have
chosen weight instead of length because length of a segment sequence means the
length of the sequence but the more important to us is the length of the shortest
