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

序列和顺序在数据中很普遍。特别是通常被视为“第四维度”的时间，在数据流和存储的时间序列数据中起着关键作用。定义事件、检测和查询噪声序列数据上的复杂事件的能力是标准数据管理系统和SQL非常需要的附加功能。这是因为复杂事件检测是关于发现同一关系中许多元组的相关性和共存性——不同于SQL中的游标模型，而且它对序列错误很敏感。本研究的目标是在高性能系统中紧密集成噪声流和存储表上的SQL查询和复杂事件检测。具体技术包括：(1)使用查询套件封装SQL查询与复杂事件检测之间的交互，提出复杂事件的综合语义；(2)将相关误差模型引入复杂事件匹配算法；(3)设计更有效的算法，只获得最高概率匹配路径的top-k，以及处理其他语义变体的算法；(4)为存储序列表设计几种索引机制，并对流和表进行整体系统优化。QUEST项目在饮食和运动监测/分析、心电监测、购物行为研究、安全监测和旅行模式发现等方面都有应用。这些应用程序在国家经济（商业智能）、健康和安全方面发挥着关键作用。该项目极大地丰富了本科定向研究性课程的课程内容，同时也为研究生开设了一门新的课程。关于该项目的更多信息可以在该项目的网页上找到：http://www.cs.uml.edu/~ge/projects/quest/。

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/ .