Event Trend Aggregation Under Rich Event Matching Semantics
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Poppe, Olga
Lei, Chuan
Rundensteiner, Elke A.
Maier, David
Streaming applications from cluster monitoring to algorithmic trading deploy Kleene queries to detect and aggregate event trends. Rich event matching semantics determine how to compose events into trends. The expressive power of state-of-the-art streaming systems remains limited since they do not support many of these semantics. Worse yet, they suffer from long delays and high memory costs because they maintain aggregates at a fine granularity. To overcome these limitations, our Coarse-Grained Event Trend Aggregation (Cogra) approach supports a rich variety of event matching semantics within one system. Better yet, Cogra incrementally maintains aggregates at the coarsest granularity possible for each of these semantics. In this way, Cogra minimizes the number of aggregates - reducing both time and space complexity. Our experiments demonstrate that Cogra achieves up to six orders of magnitude speed-up and up to seven orders of magnitude memory reduction compared to state-of-the-art approaches.
 Welcome everyone. My name is Tran Le. Today I'll present this work, Event Tran Aggregation and their reach event matching semantics. The work is in collaboration with Algar Popi, Alki Ruden-Stainer and David Mayer. Complex event processing is a technology for supporting applications such as algorithmic trading. So the CEP system continuously evaluates the cleanly pattern query against high rate streams of primitive events to detect higher level event trends. For example, in this algorithmic trading use case, it evaluates the trend aggregation query against the financial transactions streams to identify short-term profit opportunities and avoid pitfalls. So in order to deliver reliable, actionable insights about the stream, we have to consider each event in the context of other events in the stream. So in this case, a single event corresponds to a stock value. We don't know how it relates to other values. So it might be part of an uptrend or a downtrend, or it might be just an outlier. So the stock trend cannot be detected by just looking at a single event in isolation. The event sequence may also be just like a local fluctuation as part of a longer trend. So in this case, it's not a reliable insight neither. So only the event trend, which is an event sequence of any lens, can provide the reliable insights. In fact, the longer a stock trend, the more reliable it is considered by the algorithmic trading systems. So our event trend evaluation strategy must be flexible enough to ignore the local fluctuations, which is enabled by this skip to any match event matching semantics, which is commonly used in the literature. So in addition to the interest of knowing the actual event trend, actually many streaming applications are interested in the aggregated insights about these event trends. So for example, in algorithmic trading, we compute the number of downtrends per sector to predict the future trend for the same sector. And in the right sharing service, we compute the average speed of shared trip per district for the price computation, forecasting, and optimization. While detecting the trip like per driver and per rider basis, we also like to ignore some of the irrelevant events. So this behavior can be expressed by the skip to next match semantics. And lastly, the cluster monitoring tools compute, for example, the total CPU load per task that experiences continuous increasing load in order to tackle like unbalanced load distribution using automatic tuning the cluster configuration. And such query can be expressed with contiguous semantics. So the event trend analytics is complicated by the fact that the number of trends grow exponentially in the number of matched events. So for example, assuming here we have four trends created, were detected by far, and there's a new event E arrives. So this new event might be compatible with all the prefix of each existing event trend shown in green. It means this new event can be appended to these prefixes to form a new set of event trends. So the event may actually double the number of trends. In the worst case, the number of trends grow exponentially in the number of matched events. So these events can be actually of any lens. So they have this complex interdependency between among them and can be detected under various event matching semantics, which I just covered in the previous slide. Again, here in this algorithmic trading system, we consume a stream of financial transactions. And each transaction carries a sector ID, a company ID, price and the timestamp. So the query computes the number of down trends per sector to predict the future trend for this sector. The state of the art approaches basically evaluate such query in two steps. They first construct this exponentially many trends of any lens, and then they compute the aggregation. So what we propose is to eliminate this expensive trend construction step. So our proposed course grind online trend aggregation approach basically it incrementally computes the trend aggregation at the most course granularity for each event matching semantics. And these granularities range from the most course medium and then to the finest granularity. So what I mean by these like the course granularity is also called pattern grind aggregates and the medium granularity is per event type based. And the finest granularity is per matched event instance. So the number of required aggregates decreases from the most I mean the finest granularity to the course granularity. So in this way we can reduce the time complexity from exponential to quadratic in number of events in the worst case. And the space complexity can be reduced to linear as well. So here I just described our overall approach. Given the event trend aggregation query queue and the event matching semantics over an event stream. So our goal is to compute the result of the query queue with minimal latency. So in our Kagura framework to select the granularity at which the aggregates are maintained for a query queue, the static query analyzer basically analyzed the pattern of queue and classify the predicates of queue as well. And then the result of this query analysis are encoded in the Kagura configuration which is used to guide our runtime executor. So to facilitate the analysis of the query pattern we follow the traditional approach that translate the pattern query into its finite state automata based representation. We call the translated nested cleaning pattern as Kagura template and each state in the template corresponds to an event type and each transition is labeled by an operator. So based on this template we classify the event types into those that start, continue, or end a pattern. And we also determine the predecessor relationships between each event type. So based on this template we can incrementally compute the event trend count on the fly or at runtime. So here I illustrate our approach and then we skip to any match semantics. So that event is described by its type, timestamp, and count. So in this case for example A1 is an event of type A, its timestamp is 1. So the count of that event corresponds to the number of trends that end at this event. In this case the count of A1 is 1 because A1 basically starts a new event trend. And each event type in the template is associated with a count for this type. The count of a type is basically the total count of all matched events of this type. So in this case it's pretty simple. The count of type A becomes 1. And when B2 arrives it basically extends the existing trend and because B's are preceded by A's so the count of B2 becomes 1. So and then the corresponding count for the type B becomes 1 as well. And since type B is the end type in this pattern, this means that one event trend is detected. In this case it's A1 and B2. And then when A3 arrives it basically what it does is extend the existing trend. So since A's are preceded by itself and also B's, so we look up the counts from the types both A and B. And then since A by itself is a start type, so A3 starts a new trend by itself so this one is added to its count. In total the aggregate or the intermediate account for A3 is 3. And again for type the count becomes 4 that's from like A3 and also like the existing count for type A. So following the computation I just described, in this example we ended up with 43 trends detected under the skip to any match semantics and only the type grind aggregates are stored which are on the most right two columns and they're being incrementally updated and all the events which are on the left side are discarded once they have contributed to their respective counts. In particular the trends are never constructed in contrast to these state of the art approaches. So the time complexity is reduced from exponential to linear in the number of events per window which is proven to be optimal in the paper and the space complexity is also reduced to linear in the number of event types in the pattern. So the other two event matching semantics which are the skip to next match and contiguous semantics, Kogra can incrementally maintain only one aggregate per pattern. It guarantees the optimal linear time complexity while reducing the space complexity to constant. So clearly our Kogra approach is a win-win solution which enables the in-memory event trend aggregation as required by time critical applications. So we implement the Kogra in Java and conducted experiments on a single node machine with 3.4 gigahertz CPU with 128 gigabytes of memory and we evaluated our approach against three real-world datasets. So given the time of this talk we'll only show the charts using the physical activity dataset where event trends correspond to the sequence of physical activities. So we compare Kogra to four state of the art approaches and then we categorize them into let me with three different aspects. So in terms of support cleanly cloder, ACIC does not. So what we have to do is to flatten our query meaning each cleanly query is rewritten or replaced by a set of fixed-length event sequence query that covered all possible lengths of the trend. And the grata and ACIC they both only support one semantics and Flink and Sasse are the ones who use the two-step approach. So these charts compared these approaches under all three event matching semantics. The X axis show the different number of events per window and we report the latency of query execution UI axis with log scale. So our approach basically outperforms Flink and other approach by like six order of magnitude with respect to the latency for 30k event per window and or skip to any match and we observe similar performance and or skip to next match as well. Flink does perform better and are contiguous semantics because the number and length of detected trends are much less compared to other event matching semantics. Number of the less the latency of Flink is still like four orders of magnitude higher than the latency of Kogra for four million events per window. So in brief the Kogra we show is a women's solution that can achieve up to 10 to the power of six speed up and up to 10 to the power of seven memory reduction compared to these state of the art techniques. So in summary we're the first to compute aggregation of cleanly pattern queries under the rich event matching semantics with optimal time complexity. Our approach incrementally maintains event trend aggregates at the core's granularity possible for each event matching semantics and Kogra can guarantee the quadratic time complexity and linear space complexity in the number of events in the worst case. So with these measurements we can enable the real time in memory event trend aggregation as required by most time critical streaming applications. So thank you for listening and I'm happy to take questions.
 Welcome everyone. My name is Tran Le. Today I'll present this work, Event Tran Aggregation  and their reach event matching semantics. The work is in collaboration with Algar Popi,  Alki Ruden-Stainer and David Mayer.  Complex event processing is a technology for supporting applications such as algorithmic  trading. So the CEP system continuously evaluates the cleanly pattern query against high rate  streams of primitive events to detect higher level event trends. For example, in this algorithmic  trading use case, it evaluates the trend aggregation query against the financial transactions streams  to identify short-term profit opportunities and avoid pitfalls. So in order to deliver reliable,  actionable insights about the stream, we have to consider each event in the context of other  events in the stream. So in this case, a single event corresponds to a stock value. We don't know  how it relates to other values. So it might be part of an uptrend or a downtrend, or it might be  just an outlier. So the stock trend cannot be detected by just looking at a single event in  isolation. The event sequence may also be just like a local fluctuation as part of a longer trend.  So in this case, it's not a reliable insight neither. So only the event trend, which is an event  sequence of any lens, can provide the reliable insights. In fact, the longer a stock trend,  the more reliable it is considered by the algorithmic trading systems. So our event trend  evaluation strategy must be flexible enough to ignore the local fluctuations, which is enabled  by this skip to any match event matching semantics, which is commonly used in the literature.  So in addition to the interest of knowing the actual event trend, actually many streaming  applications are interested in the aggregated insights about these event trends. So for example,  in algorithmic trading, we compute the number of downtrends per sector to predict the future trend  for the same sector. And in the right sharing service, we compute the average speed of shared  trip per district for the price computation, forecasting, and optimization. While detecting  the trip like per driver and per rider basis, we also like to ignore some of the irrelevant  events. So this behavior can be expressed by the skip to next match semantics. And lastly,  the cluster monitoring tools compute, for example, the total CPU load per task that experiences  continuous increasing load in order to tackle like unbalanced load distribution using automatic  tuning the cluster configuration. And such query can be expressed with contiguous semantics.  So the event trend analytics is complicated by the fact that the number of trends grow exponentially  in the number of matched events. So for example, assuming here we have four trends created,  were detected by far, and there's a new event E arrives. So this new event might be compatible  with all the prefix of each existing event trend shown in green. It means this new event  can be appended to these prefixes to form a new set of event trends. So the event may  actually double the number of trends. In the worst case, the number of trends grow exponentially  in the number of matched events. So these events can be actually of any lens. So they have  this complex interdependency between among them and can be detected under various event  matching semantics, which I just covered in the previous slide. Again, here in this algorithmic  trading system, we consume a stream of financial transactions. And each transaction carries  a sector ID, a company ID, price and the timestamp. So the query computes the number of down  trends per sector to predict the future trend for this sector. The state of the art approaches  basically evaluate such query in two steps. They first construct this exponentially many  trends of any lens, and then they compute the aggregation. So what we propose is to  eliminate this expensive trend construction step. So our proposed course grind online  trend aggregation approach basically it incrementally computes the trend aggregation at the most  course granularity for each event matching semantics. And these granularities range from  the most course medium and then to the finest granularity. So what I mean by these like  the course granularity is also called pattern grind aggregates and the medium granularity  is per event type based. And the finest granularity is per matched event instance. So the number  of required aggregates decreases from the most I mean the finest granularity to the  course granularity. So in this way we can reduce the time complexity from exponential  to quadratic in number of events in the worst case. And the space complexity can be reduced  to linear as well. So here I just described our overall approach. Given the event trend  aggregation query queue and the event matching semantics over an event stream. So our goal  is to compute the result of the query queue with minimal latency. So in our Kagura framework  to select the granularity at which the aggregates are maintained for a query queue, the static  query analyzer basically analyzed the pattern of queue and classify the predicates of queue  as well. And then the result of this query analysis are encoded in the Kagura configuration  which is used to guide our runtime executor. So to facilitate the analysis of the query  pattern we follow the traditional approach that translate the pattern query into its  finite state automata based representation. We call the translated nested cleaning pattern  as Kagura template and each state in the template corresponds to an event type and each transition  is labeled by an operator. So based on this template we classify the event types into  those that start, continue, or end a pattern. And we also determine the predecessor relationships  between each event type. So based on this template we can incrementally compute the  event trend count on the fly or at runtime. So here I illustrate our approach and then  we skip to any match semantics. So that event is described by its type, timestamp, and count.  So in this case for example A1 is an event of type A, its timestamp is 1. So the count  of that event corresponds to the number of trends that end at this event. In this case  the count of A1 is 1 because A1 basically starts a new event trend. And each event type  in the template is associated with a count for this type. The count of a type is basically  the total count of all matched events of this type. So in this case it's pretty simple.  The count of type A becomes 1. And when B2 arrives it basically extends the existing  trend and because B's are preceded by A's so the count of B2 becomes 1. So and then  the corresponding count for the type B becomes 1 as well. And since type B is the end type  in this pattern, this means that one event trend is detected. In this case it's A1 and  B2. And then when A3 arrives it basically what it does is extend the existing trend.  So since A's are preceded by itself and also B's, so we look up the counts from the types  both A and B. And then since A by itself is a start type, so A3 starts a new trend by  itself so this one is added to its count. In total the aggregate or the intermediate  account for A3 is 3. And again for type the count becomes 4 that's from like A3 and also  like the existing count for type A. So following the computation I just described, in this  example we ended up with 43 trends detected under the skip to any match semantics and  only the type grind aggregates are stored which are on the most right two columns and  they're being incrementally updated and all the events which are on the left side are  discarded once they have contributed to their respective counts. In particular the trends  are never constructed in contrast to these state of the art approaches. So the time complexity  is reduced from exponential to linear in the number of events per window which is proven  to be optimal in the paper and the space complexity is also reduced to linear in the number of  event types in the pattern. So the other two event matching semantics which are the skip  to next match and contiguous semantics, Kogra can incrementally maintain only one aggregate  per pattern. It guarantees the optimal linear time complexity while reducing the space complexity  to constant. So clearly our Kogra approach is a win-win solution which enables the in-memory  event trend aggregation as required by time critical applications. So we implement the  Kogra in Java and conducted experiments on a single node machine with 3.4 gigahertz CPU  with 128 gigabytes of memory and we evaluated our approach against three real-world datasets.  So given the time of this talk we'll only show the charts using the physical activity  dataset where event trends correspond to the sequence of physical activities. So we compare  Kogra to four state of the art approaches and then we categorize them into let me with  three different aspects. So in terms of support cleanly cloder, ACIC does not. So what we  have to do is to flatten our query meaning each cleanly query is rewritten or replaced  by a set of fixed-length event sequence query that covered all possible lengths of the trend.  And the grata and ACIC they both only support one semantics and Flink and Sasse are the ones  who use the two-step approach. So these charts compared these approaches under all three  event matching semantics. The X axis show the different number of events per window and  we report the latency of query execution UI axis with log scale. So our approach basically  outperforms Flink and other approach by like six order of magnitude with respect to the  latency for 30k event per window and or skip to any match and we observe similar performance  and or skip to next match as well. Flink does perform better and are contiguous semantics  because the number and length of detected trends are much less compared to other event  matching semantics. Number of the less the latency of Flink is still like four orders  of magnitude higher than the latency of Kogra for four million events per window. So in  brief the Kogra we show is a women's solution that can achieve up to 10 to the power of  six speed up and up to 10 to the power of seven memory reduction compared to these state  of the art techniques. So in summary we're the first to compute aggregation of cleanly  pattern queries under the rich event matching semantics with optimal time complexity. Our  approach incrementally maintains event trend aggregates at the core's granularity possible  for each event matching semantics and Kogra can guarantee the quadratic time complexity  and linear space complexity in the number of events in the worst case. So with these  measurements we can enable the real time in memory event trend aggregation as required  by most time critical streaming applications. So thank you for listening and I'm happy to  take questions.
Poppe_Lei_Rundensteiner_Maier_0_131.png Poppe_Lei_Rundensteiner_Maier_132_239.png Poppe_Lei_Rundensteiner_Maier_240_347.png Poppe_Lei_Rundensteiner_Maier_348_491.png Poppe_Lei_Rundensteiner_Maier_492_1895.png Poppe_Lei_Rundensteiner_Maier_1896_2915.png Poppe_Lei_Rundensteiner_Maier_2916_3767.png Poppe_Lei_Rundensteiner_Maier_3768_5963.png Poppe_Lei_Rundensteiner_Maier_5964_6827.png Poppe_Lei_Rundensteiner_Maier_6828_7823.png Poppe_Lei_Rundensteiner_Maier_7824_8627.png Poppe_Lei_Rundensteiner_Maier_8628_9083.png Poppe_Lei_Rundensteiner_Maier_9084_10823.png Poppe_Lei_Rundensteiner_Maier_10824_12011.png Poppe_Lei_Rundensteiner_Maier_12012_12947.png Poppe_Lei_Rundensteiner_Maier_12948_13175.png Poppe_Lei_Rundensteiner_Maier_13176_13319.png Poppe_Lei_Rundensteiner_Maier_13320_13583.png Poppe_Lei_Rundensteiner_Maier_13584_15191.png Poppe_Lei_Rundensteiner_Maier_15192_16727.png Poppe_Lei_Rundensteiner_Maier_16728_17747.png Poppe_Lei_Rundensteiner_Maier_17748_19211.png Poppe_Lei_Rundensteiner_Maier_19212_20075.png Poppe_Lei_Rundensteiner_Maier_20076_21143.png Poppe_Lei_Rundensteiner_Maier_21144_23111.png Poppe_Lei_Rundensteiner_Maier_23112_24311.png Poppe_Lei_Rundensteiner_Maier_24312_24419.png Poppe_Lei_Rundensteiner_Maier_24420_24550.png