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

path it actually represents. Therefore, if we want to compute all the paths to
the length l we have to store all the segment sequences having its weight less or
equal to l . This parameter l then forms a path length limit that is to be indexed.
Seemingly, to compute the weight of the sequence of segments ( S 1 ...S l )we
would have to compute all its connecting paths to find out which of them is
the shortest. But an enhanced algorithm does not compute all the connecting
paths but only one shortest connecting path for each combination of common
edges picked from all CE i s, see Definition 4. Thus we have an upper bound on
a number of connecting paths to be computed for each sequence of segments.
Due to the fact that the weight of a segment sequence represents the length of
a shortest path it represents, it also represents some of the paths that are longer
then its minimal weight. Therefore, using ρ -index we can compute surely all the
paths to the length l but also some of the paths that are actually longer than
the specified l . As we will show in the evaluation in Section 10.5 the amounts
of paths longer then l is not insignificant, yet we realize that this fact highly
depends on the nature of the data on which the ρ -index is being used.

10.4 The Search Algorithm

In this section we describe the algorithm for discovery of all paths to a certain
length between two vertices in the indexed graph using ρ -index. Firstly, the
algorithm looks up the segments the start and end vertex are assigned to. If
we have more than two levels in the ρ -index it looks up to which segments on
the upper level are assigned the segments acquired in the previous step. This
continues until we reach the top level of the ρ -index or we get one common
segment for both vertices. This process goes from the bottom of the structure to
the top. From the definition of the graph segmentation each vertex or segment
belongs to one segment on the upper level. Therefore, for each vertex in the
original graph only one segment exists at each level that contains it.

10.4.1 The Transcription Graph

A special graph structure is used to represent the result throughout the algorithm
computation. It is a transcription graph where the vertices and edges are replaced
by subgraphs retrieved from the ρ -index. The vertices in the transcription graph
are either the segments of the ρ -index or the vertices of the indexed graph. Those
are considered to form the lowest level of the ρ -index. The transcription graph
contains four special kinds of edges:

transitionTo denotes an existence of a transition (edge) between vertices at
the particular level.
existsPathTo indicates an edge that can be replaced by a subgraph from ρ -
index consisting of vertices at the same level and transitions between them,
representing all sequences of segments lying between these two vertices. This
edge may be only between two vertices that are assigned to one common
segment on a higher level.