Indexing Structure for Graph-Structured Data - Mining Complex Data - page 169

a graphs of a similar size and connectivity. In this case the category is formed
by graphs having from 10,000 to 30,000 vertices and 20,000 to 60,000 edges
respectively.

10.5.2 Search Complexity

This group of experiments performed describe the complexity of the search algo-
rithm using the ρ -index to search all paths to a certain length in respect to the
size of the graph on which the search was performed. Figure 10.11 demonstrates
the experiments where the parameter settings were fixed and the size of the
graph grew. As we mentioned earlier in this section, the result of the search of
the larger graph contains all the search results of the smaller graphs, thus they
are comparable.
Both parts of Figure 10.11 refer to the same results of the same experiments.
They only differ in the y-axis scale. The left part depicts the results in the whole
scale, the right part depicts them ranging from 0 to 80,000 of processed vertices.
The particular curves represent the algorithms used to perform the search
of all paths lying between two vertices. The lines labeled with the prefix seq
represent a sequential algorithm. This algorithm represents an upper bound of
a way to solve the problem of searching all path between two vertices to a
certain length. It is a depth first search that tries to recursively build a path of
a some maximum length. The number in the label states the maximal length of
a searched path.
In Figure 10.11 are present two results for a sequential algorithm seq .Thisis
caused by the nature of the ρ -index and its search algorithm which results in
a fact that all paths to a specified length l to which the ρ -index was built are
returned and some of the paths longer than l are also returned by the search
algorithm. That implies for the result of the search using ρ -index that is true:
seq ( l ) seq ( l + k ) for a particular k , where the set inclusion is meant

on the results of the search algorithms. For that reason we also present the
complexity of the algorithm seq (12) which represents the sequential scan for all

⊆ ρ -index ⊆

700000 80000

rhoIndex
n*log(m)
seq(10)
seq(12)

rhoIndex
n*log(m)
seq(10)

70000

600000

60000

500000

50000

400000

40000

300000

30000

200000

20000

100000

10000

0 0

5000 10000 15000 20000 25000 30000 5000 10000 15000 20000 25000 30000

number of vertices in a graph number of vertices in a graph

Fig. 10.11. A ρ -index search complexity with respect to the graph size