Detecting Imperfect Patterns in Event Streams Using Local Search

Adele E. Howe

Computer Science Department
Colorado State University
Fort Collins, CO 80523
USA
howe@cs.colostate.edu

Abstract:

Recurring patterns in event streams may indicate causal influences. Such patterns have been used as the basis of software debugging. One technique, dependency detection, for finding these patterns requires exhaustive search and perfect patterns, two characteristics that are unrealistic for event streams extracted from software executions. This paper presents an enhanced version of dependency detection that uses a more flexible pattern matching scheme to extend the types of patterns detected and local search to reduce the computational demands. The new version was tested on real and artificial data to determine whether local search is effective for detecting strong patterns.

• Introduction
• Finding Significant Sequences
  • Dependency Detection
  • Local Search Dependency Detection
    • Improving the Matching
    • Reducing the Search
• Results
  • Finding Dependencies in Phoenix Data
  • Finding Dependencies in Synthetic Data
• Conclusions