Skip to main content

Carlea Holl-Jensen||cholljen@umd.edu


HCIL-2009-14

Wang, T., Deshpande, A., Shneiderman, B. (May 2009)
A Temporal Pattern Search Algorithm for Personal History Event Visualization
Wang, T.; Deshpande, A.; Shneiderman, B.; , "A Temporal Pattern Search Algorithm for Personal History Event Visualization," Published in Knowledge and Data Engineering, IEEE Transactions on, vol.PP, no.99, pp.1, 0.
doi: 10.1109/TKDE.2010.257 [Published Version]
HCIL-2009-14

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(m^2 n lg(n)), where m is the number of items in a search pattern, and n is the number of events in a history. Although the asymptotic running time of TPS is inferior to that of a non-deterministic finite automaton (NFA) approach (O(mn)), TPS performs better than NFA under our experimental conditions. We also show TPS is very competitive to Shift-And, a bit-parallelism 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.



EventFlow Screenshot

EventFlow
More information

Tech Reports
Video Reports
Annual Symposium

News
Seminars + Events
Calendar
HCIL Seminar Series
Annual Symposium
HCIL Service Grants
Events Archives
Awards
HCIL Conference Travel Award
Job Openings
For the Press
HCIL Overview
Become a Member
Collaborators
Collaborating Groups + People
Academic Visitors
Join our Mailing List
Contact Us
Visit Us
HCIL Store
Give the HCIL a Hand
HCIL T-shirts for Sale
Our Lighter Side
HCIL Memories Page
Faculty/ Staff
Students
Ph.D. Alumni
Past Members
Research Areas
Communities
Design Process
Digital Libraries
Education
Physical Devices
Public Access
Visualization
Research Histories
Faculty Listed by Research
Project Highlights
Project Screenshots
Publications and TRs
Videos
Books
Products
Presentations
Studying HCI
Masters in HCI
PhD in HCI
Visiting Scholars
Class Websites
Sponsor our Research
Sponsor our Annual Symposium
Active Sponsorship
Industrial Visitors