The efficacy of local search was tested on some data sets from
Phoenix. The results were similar in each data set and are reported
for a data set with 946 events (alternating failures and recovery
actions) in its event streams. For each of eight target failures
(those that appeared in the event streams at least five times), the
algorithm started with 100 randomly generated precursors of length
three (which makes a pattern of length 4) using a window size of seven
and searched for the highest rated neighbor that could be reached from
each. Each precursor included either failures or recovery actions for
18 possible values in each precursor position. The searches found a
significant dependency in about one-third of the trials, and half were
highly significant (*p* ;*SPMlt*; .01). As would be expected, many of the
dependencies were found in more than one trial and significant
dependencies tended to be related to other significant
dependencies. Table 1.2 summarizes the results for each
target failure (designated by number) by number of unique dependencies
found, number of dependencies found with *p* ;*SPMlt*; .01, and the average
search depth to find the dependencies. The search depth suggests a
strong relationship between significant patterns and indicates the
number of times the operator was applied. The 100 trials on the eight
failures required three hours of CPU time on a SPARC IPX with the code
written in Lucid Common Lisp.

**Table 1.2:** Results of local search for 8 target failures with precursors
of length 3, window of length 7 on a Phoenix data set. The first two rows
represent the number of trials out of 100 which found unique patterns
and highly significant patterns. The last row indicates the average number of
applications of the local search operator during a trial.

As shown in Table 1.3, searching for length four precursors exhibited similar, if slightly less successful results. Highly significant dependencies are found in, on average, 18 out of 200 trials. In this case, the search tends to proceed much further, but this is balanced out by many of the initial starts not appearing in the data and many of their neighbors not appearing in the data either. Not too surprisingly, the 200 trials on the eight failures required twice as much computation (six hours).

**Table 1.3:** Results for precursors of length 4, window of
length 9

As would be expected, the dependencies found exhibited a high degree of overlap. As described earlier, a shorter pattern overlaps with a longer pattern when the longer pattern is the shorter pattern with events added to one or the other end. Over 50% of the length three precursors overlapped (i.e., were substrings) of the length four precursors. Additionally, comparisons to exhaustive search of longer dependencies showed overlap as well: nearly all the relative order dependencies were found within the absolute order dependencies.

Wed Mar 6 09:01:10 MST 1996