III: Small: QUEST: An Integrated Query and Event System on Noisy Streams and Tables

University Of Massachusetts Lowell, Lowell MA

Investigators

Abstract

Sequence and order are prevalent in data. In particular, time, as often perceived as the "fourth dimension", plays a pivotal role in data streams as well as in stored time series data. The ability to define events, detect and query complex events over noisy sequence data is a much needed addition to the standard data management systems and SQL. This is because complex event detection is about discovering the correlation and co-occurrence of many tuples in the same relation - different from the cursor model in SQL, and because it is sensitive to sequence errors. The goal of this research is to tightly integrate SQL queries and complex event detection over noisy streams and stored tables in a high-performing system. Specific techniques include: (1) Using a query suite to encapsulate the interactions between SQL queries and complex event detection, and proposing a comprehensive semantics for complex events; (2) Incorporating correlated error models into a novel complex event matching algorithm; (3) Designing more efficient algorithms that only get the top-k highest probability matching paths, as well as algorithms that handle other variants of semantics; and (4) Devising several indexing mechanisms for stored sequence tables, and performing overall system optimization for both streams and tables. The QUEST project has applications in dietary and exercise monitoring/analysis, ECG monitoring, shopping behavior study, security monitoring, and travel pattern discovery, among many others. These applications play a key role in the nation's economy (business intelligence), health, and security. The project greatly enriches the course contents of the undergraduate directed research course in addition to a new graduate course. Further information on the project can be found on the project web page: http://www.cs.uml.edu/~ge/projects/quest/ .