next up previous
Next: Improving the Matching Up: Finding Significant Sequences Previous: Dependency Detection

Local Search Dependency Detection

Dependency detection is limited primarily by its reliance on exhaustive search of possible patterns. This was feasible initially because the search space included only all possible immediately preceding influences on failure; the traces contained at most eleven types of failure and eight recovery actions, producing, at most, 1177 possible combinations.

The original algorithm was modified to include more flexible matching and a non-exhaustive, but computationally more manageable search through local search. More flexible matching of patterns to data means that the event streams may be composed of many types of events, which need not alternate as beforegif. The events can be of different values for several types. Any set of events with time stamps for ordering is a legal event stream. In this view, the event streams for the Phoenix data are described as having two types of events, failures and recovery actions, which include eleven and eight values respectively. The data is passed to the program in a file with three columns: time stamp, event type and event value.

adele howe
Wed Mar 6 09:01:10 MST 1996