Discovering Episodes with Compact Minimal Windows
  Discovering the most interesting patterns is the key problem in the field of
pattern mining. While ranking or selecting patterns is well-studied for
itemsets it is surprisingly under-researched for other, more complex, pattern
types.
  In this paper we propose a new quality measure for episodes. An episode is
essentially a set of events with possible restrictions on the order of events.
We say that an episode is significant if its occurrence is abnormally compact,
that is, only few gap events occur between the actual episode events, when
compared to the expected length according to the independence model. We can
apply this measure as a post-pruning step by first discovering frequent
episodes and then rank them according to this measure.
  In order to compute the score we will need to compute the mean and the
variance according to the independence model. As a main technical contribution
we introduce a technique that allows us to compute these values. Such a task is
surprisingly complex and in order to solve it we develop intricate finite state
machines that allow us to compute the needed statistics. We also show that
asymptotically our score can be interpreted as a P-value. In our experiments we
demonstrate that despite its intricacy our ranking is fast: we can rank tens of
thousands episodes in seconds. Our experiments with text data demonstrate that
our measure ranks interpretable episodes high.
