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.