TY - JOUR
T1 - A Temporal Pattern Search Algorithm for Personal History Event Visualization
JF - Knowledge and Data Engineering, IEEE Transactions on
Y1 - 2012
A1 - Wang,T. D
A1 - Deshpande, Amol
A1 - Shneiderman, Ben
KW - automaton-based approach
KW - binary search
KW - bit-parallel approach
KW - data visualisation
KW - electronic health records
KW - event array
KW - finite automata
KW - interactive visualization program
KW - Lifelines2 visualization tool
KW - medical information systems
KW - NFA approach
KW - nondeterministic finite automaton
KW - O(m2n lg(n)) problem
KW - pattern matching
KW - personal history event visualization
KW - Shift-And approach
KW - temporal pattern search algorithm
KW - time stamp
AB - We present Temporal Pattern Search (TPS), a novel algorithm for searching for temporal patterns of events in historical personal histories. The traditional method of searching for such patterns uses an automaton-based approach over a single array of events, sorted by time stamps. Instead, TPS operates on a set of arrays, where each array contains all events of the same type, sorted by time stamps. TPS searches for a particular item in the pattern using a binary search over the appropriate arrays. Although binary search is considerably more expensive per item, it allows TPS to skip many unnecessary events in personal histories. We show that TPS's running time is bounded by O(m2n lg(n)), where m is the length of (number of events) a search pattern, and n is the number of events in a record (history). Although the asymptotic running time of TPS is inferior to that of a nondeterministic finite automaton (NFA) approach (O(mn)), TPS performs better than NFA under our experimental conditions. We also show TPS is very competitive with Shift-And, a bit-parallel approach, with real data. Since the experimental conditions we describe here subsume the conditions under which analysts would typically use TPS (i.e., within an interactive visualization program), we argue that TPS is an appropriate design choice for us.
VL - 24
SN - 1041-4347
CP - 5
M3 - 10.1109/TKDE.2010.257
ER -