Discovering unexpected patterns in temporal data using temporal logic. Temporal Databases: research and practice

Abstract. There has been much attention given recently to the task of finding interesting patterns in temporal databases. Since there are so many different approaches to the problem of discovering temporal pat-terns, we first present a characterization of different discovery tasks and then focus on one task of discovering interesting patterns of events in temporal sequences. Given an (infinite) temporal database or a sequence of events one can, in general, discover an infinite number of temporal patterns in this data. Therefore, it is important to specif\ ' some measure of interestingness for discovered patterns and then select only the pat-terns interesting according to this measure. if'e present a probabitistic measure of interestingness based on unezpectedness, whereby a pattern P is deemed interesting if the ratio of the actual number of occurrences of P exceeds the ezpected number of occurrences of P by some user defined threshold. We then make use o fa subset of the propositional, linear tem-poral logic and present an efficient algorithm that discovers unexpected patterns in temporal data. Finally, we apply this algorithm to synthetic data, UNIX operating system calls, and \Veb logfiles and present the results of these experiments.