DISCOVERING FREQUENT EVENT PATTERNS WITH MULTIPLE GRANULARITIES IN TIME SEQUENCES

An important usage of time sequences is to discover temporal patterns. The discovery process usually starts with a user-specified skeleton, called an event structure, which consists of a number of variables rep resenting events and temporal constraints among these variables; the g oal of the discovery is to find temporal patterns, i.e., instantiation s of the variables in the structure that appear frequently in the time sequence. This paper introduces event structures that have temporal c onstraints with multiple granularities, defines the pattern-discovery problem with these structures, and studies effective algorithms to sol ve it. The basic components of the algorithms include timed automata w ith granularities (TAGs) and a number of heuristics. The TAGs are for testing whether a specific temporal pattern, called a candidate comple x event type, appears frequently in a time sequence. Since there are o ften a huge number of candidate event types for a usual event structur e, heuristics are presented aiming at reducing the number of candidate event types and reducing the time spent by the TAGs testing whether a candidate type does appear frequently in the sequence. These heuristi cs exploit the information provided by explicit and implicit temporal constraints with granularity in the given event structure. The paper a lso gives the results of an experiment to show the effectiveness of th e heuristics on a real data set.