  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.
