5
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      GRETA: Graph-based Real-time Event Trend Aggregation

      Preprint
      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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.

          Related collections

          Author and article information

          Journal
          06 October 2020
          Article
          2010.02988
          471d2196-be67-4958-8742-aa86a1ed47e5

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Technical report for the paper in VLDB 2017
          cs.DS cs.DB cs.PF

          Databases,Data structures & Algorithms,Performance, Systems & Control
          Databases, Data structures & Algorithms, Performance, Systems & Control

          Comments

          Comment on this article