Information Technology Reference
In-Depth Information
the testing start and end vertex actually present in G1000 is 1821 and the amount
of paths of length 14 between the same two vertices is 12644. So even if we find
really low percentage of the paths present in the indexed graph, their amount
can easily reach tens of thousands. For illustration, for the
sof tL
=
l
=10and
a path length of 24 the amount of found paths is 72,000 and the longest found
path has a length of 42.
10.5.4
Search Complexity Affected by the Parameter Settings
Since the
ρ
-index can be created for one particular graph using different pa-
rameter settings and as we could see from this section, also having different
properties, we explore the correlation between certain parameter setting and the
complexity of the searches performed on the respective indexing structures built
upon one particular testing graph.
Again we have chosen the testing graph G10000. The parameter settings dif-
fered in the maximal size of a segment on the lowest level, the upper level
settings remained the same for all tests. Consequently, Figure 10.14 depicts the
relation between the parameter settings and the average search complexity for
thus created
ρ
-index. This curve is falling with the increase of the cluster size.
The dashed curve in Figure 10.14 reflects the creation time of the
ρ
-index for
that particular parameter setting. The time is in minutes multiplied by 1000
to make the curve visible in this scale. On the contrary, the progress of this
curve is rising as the
ρ
-index structure is becoming underfilled. We have already
seen this behavior in Figure 10.10 at all graph sizes at the rising part of the
parabolas.
60000
search complexity
creation time (mins*1000)
50000
40000
30000
20000
10000
0
20
25
30
35
40
45
50
lowest level cluster size
Fig. 10.14.
A
ρ
-index search complexity related to the parameter setting
