Testing complex temporal relationships involving multiple granularities and its application to data mining

An important usage of time sequences is for discovering temporal patterns of events (a special type of data mining). This process usually starts with the specification by the user of an event structure which consists of a number of variables representing events and temporal constraints among these variables. The goal of the data mining is to find temporal patterns, i.e., instantiations of the variables in the structure, which frequently appear in the time sequence. This paper introduces event structures that have temporal constraints with multiple granularities (TCGs). Testing the consistency of such structures is shown to be NP-hard. An approximate algorithm is then presented. The paper also introduces the concept of a timed automation with granularities (TAGs) that can be used to find in a time sequence occurrences of a particular TCG with instantiated variables. The TCGs, the approximate algorithm and the TAGs are shown to be useful for obtaining effective data mining procedures.