论文标题
Greta：基于图的实时事件趋势聚合
GRETA: Graph-based Real-time Event Trend Aggregation
论文作者
论文摘要
从算法交易到流量管理部署Kleene模式的流媒体应用程序，以检测和汇总任意长的事件序列，称为事件趋势。最先进的系统分两个步骤处理此类查询。也就是说，他们首先构建了所有趋势，然后汇总它们。由于趋势构建的指数成本，这种两步的方法既延迟延迟又遭受了高度的记忆成本。为了克服这些局限性，我们提出了基于图的实时事件趋势聚合（GRETA）方法，该方法在不先构建这些趋势的情况下动态计算事件趋势聚集。我们将Greta图定义为紧凑地编码所有趋势。我们的Greta运行时会逐步维护图形，同时沿其边缘动态传播聚合物。基于图表，最终的骨料会逐渐更新，并在每个查询窗口的末尾即时返回。我们的GRETA运行时代表了双赢解决方案，从指数到二次的时间复杂性以及事件数量中从指数到线性的空间复杂性降低了时间复杂性。我们的实验表明，与最先进的两步方法相比，Greta最多达到了多达四个数量级的速度和最多50倍的记忆。
Streaming applications from algorithmic trading to traffic management deploy Kleene patterns to detect and aggregate arbitrarily-long event sequences, called event trends. State-of-the-art systems process such queries in two steps. Namely, they first construct all trends and then aggregate them. Due to the exponential costs of trend construction, this two-step approach suffers from both a long delays and high memory costs. To overcome these limitations, we propose the Graph-based Real-time Event Trend Aggregation (Greta) approach that dynamically computes event trend aggregation without first constructing these trends. We define the Greta graph to compactly encode all trends. Our Greta runtime incrementally maintains the graph, while dynamically propagating aggregates along its edges. Based on the graph, the final aggregate is incrementally updated and instantaneously returned at the end of each query window. Our Greta runtime represents a win-win solution, reducing both the time complexity from exponential to quadratic and the space complexity from exponential to linear in the number of events. Our experiments demonstrate that Greta achieves up to four orders of magnitude speed-up and up to 50--fold memory reduction compared to the state-of-the-art two-step approaches.
