Tech Report HCIL-2009-14
|
Wang, T., Deshpande, A., Shneiderman, B. (May 2009) Abstract—We present Temporal Pattern Search (TSS), a novel algorithm for searching for temporal patterns of events (and absence of events). The traditional method of searching for such patterns uses an automaton-based approach over a single array of events, sorted by time stamps. Instead, TSS operates on a set of arrays, where each array contains all events of the same type, sorted by time stamps. TSS searches for a particular item in the pattern using a binary search over an array for each event type. Although it is considerably more expensive per item, it allows TSS to skip many unnecessary events from the input of events. We show that TSS’s running time is bounded by O(m2n lg(n)), where m is the number of items in a search pattern, and n is the number of events in the input. We also show that although the asymptotic running time of TSS is inferior to that of a non-deterministic finite automaton (NFA) approach (O(mn)), under our experimental conditions, TSS consistently outperforms NFA. Since the experimental conditions we describe here subsume the conditions under which users would typically use TSS (i.e. within an interactive visualization), we argue that TSS is the appropriate design choice for us. Furthermore, TSS and the strategy to split input data into several sorted arrays is generalizable to other applications. 
|
