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

X Y

K L

(3, 3, 1) (4, 3, 2)

E F

(2, 2, 1)

(5, 2, 2)

v 1 v 10

(1, 1, 1)

(6, 1, 2)

(0, 0, 1)

(7, 0, 2)

edges:

segment name

transitionTo
existsPathTo

Y
(4, 3, 1)

min path weight from start

order from left isSuperiorToRight

belongsToRight

level number

Fig. 10.4. Example of an initial transcription graph

belongsToRight represents the relationship of containment, a vertex from a
lower level belongs to a vertex on a higher level.
isSuperiorToRight is an opposite of the previous relationship, it means that
the vertex at a higher level contains the vertex on a lower level.

Figure 10.4 demonstrates an initial state of the transcription graph for a search
of all paths between vertices 1 and 10 in ρ -index having four levels. The vertices
are assigned to respective segments on upper levels and on the topmost level an
existence of a path is supposed between the segments at the highest level.
The concept of the transcription process is to take the initial transcription
graph and transform it to a graph which comprises of only vertices at the lowest
level and all edges are of the transitionTo type. To achieve this, all the segments
and edges at the higher levels need to be processed - transcribed - into entities
at lower levels until we achieve the stop condition of the algorithm. Firstly, it re-
places the existsPathTo edge by a respective subgraph of sequences of segments
lying between the two vertices where all the edges are transitions. Secondly, all
of the transitions concerning the particular segment, that is to be transformed
into entities on the lower level, each transition originated or terminated at this
segment is replaced by a subgraph of segments at a lower level connected to
this segment by the type of edges connecting segments on different levels. This
transformation is demonstrated in Figure 10.5 as the first step in the process.
The transition between the segments X and Z is transformed into a transition
between segments L and K , but on a lower level. This fact indicates, that there
exists a border edge between segments X and Y which is originated in K and ter-
minated in L ,where K belongs to segment X and L is assigned to segment Y .If
there existed any other border edges they would also appear in the transcription
graph at this point.