Efficient Query Processing for Dynamically Changing Datasets
Efficient Query Processing for Dynamically Changing Datasets
复制标题
DOI：
10.1145/3371316.3371325
复制
发表时间：
2019-03-01
期刊：
影响因子：
1.1
通讯作者：
Lehner, Wolfgang
中科院分区：
文献类型：
--
作者：
Idris, Muhammad;Ugarte, Martin;Lehner, Wolfgang
高效分析不断变化的数据的能力是许多实时分析应用程序的关键要求。解决这个问题的传统方法是围绕增量视图维护(IVM)的概念发展起来的，并且要么基于子结果的物化(以避免它们的重新计算)，要么基于子结果的重新计算(以避免物化的空间开销)。这两种技术都不是最优的：除了物化结果和子结果，还可以维护一个数据结构，该数据结构支持在更新下的有效维护，并且可以从该数据结构快速枚举完整的查询结果。在前两篇文章中，我们介绍了用于动态评估查询的算法，这些算法易于实现、高效，并且可以自然地扩展以评估来自广泛应用程序领域的查询。在本文中，我们讨论了我们的算法及其复杂性，解释了其效率背后的主要组成部分。最后，我们给出了实验，将我们的算法与最先进的(高阶)IVM引擎以及著名的复杂事件识别引擎进行了比较。我们的方法比竞争对手的系统在处理时间上高出两个数量级，在内存消耗上高出一个数量级。
The ability to efficiently analyze changing data is a key requirement of many real-time analytics applications. Traditional approaches to this problem were developed around the notion of Incremental View Maintenance (IVM), and are based either on the materialization of subresults (to avoid their recomputation) or on the recomputation of subresults (to avoid the space overhead of materialization). Both techniques are suboptimal: instead of materializing results and subresults, one may also maintain a data structure that supports efficient maintenance under updates and from which the full query result can quickly be enumerated. In two previous articles, we have presented algorithms for dynamically evaluating queries that are easy to implement, efficient, and can be naturally extended to evaluate queries from a wide range of application domains. In this paper, we discuss our algorithm and its complexity, explaining the main components behind its efficiency. Finally, we show experiments that compare our algorithm to a state-of-the-art (Higher-order) IVM engine, as well as to a prominent complex event recognition engine. Our approach outperforms the competitor systems by up to two orders of magnitude in processing time, and one order in memory consumption.