Databases Reference
In-Depth Information
FIGURE 3.5: Example of score computation for pair (b;f) in the APTA in
Figure 3.4.
because \close" is possible from b, but not from c. Any pair that involves node
a produces a score of 0, because \load" only appears once in the machine.
3.3.2.2
Blue-Fringe Search Strategy
It becomes apparent that computing the score for every pair of states at
every iteration of the algorithm can become very expensive. The problem is
amplified when we are dealing with non-trivial state machines, or PTAs that
are generated from large trace sets. The Blue-Fringe strategy [19] is a win-
dowing method for limiting the number of pairs of nodes that have to be
compared to each other. The algorithm keeps a list of nodes that are mutu-
ally unmergable, which reduces the number of state comparisons by orders of
magnitude.
In terms of the EDSM algorithm shown in algorithm 2, the Blue-Fringe
strategy is implemented as part of the selectStatePairs function. It operates
by coloring the states of the state machine such that unmergable pairs are red,
and candidates to be compared to the red states are colored blue. To begin
with, the initial state is colored red, and its neighbouring states are colored
blue (the rest remain uncolored). Every red-blue pair of nodes is compared
according to the EDSM algorithm shown above, and the pairs are ranked.
If a blue state cannot be merged to any red state, it is colored red and the
process iterates. Otherwise, if none of the red-blue pairs are incompatible,
they are ranked according to their similarity scores and merged, starting with
the highest-scoring and finishing with the lowest scoring pair. Every time a
pair is merged the blue state disappears since it is merged into a red node.
As an example, we refer to Figure 3.4. Let us imagine that nodes a and b
are red, and that nodes c and d form the blue fringe. If d is merged to b, the
merged state bd becomes red. Once there are no further merges to be carried
out, the blue-fringe is recomputed, nodes c, f, and g are colored blue, and
the whole process iterates until all nodes in the state machine are red. For a
Search WWH ::
Custom Search