{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T10:01:34Z","timestamp":1773482494453,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3151113.3151120","type":"journal-article","created":{"date-parts":[[2017,10,19]],"date-time":"2017-10-19T12:30:08Z","timestamp":1508416208000},"page":"80-92","source":"Crossref","is-referenced-by-count":10,"title":["GRETA"],"prefix":"10.14778","volume":"11","author":[{"given":"Olga","family":"Poppe","sequence":"first","affiliation":[{"name":"Worcester Polytechnic Institute"}]},{"given":"Chuan","family":"Lei","sequence":"additional","affiliation":[{"name":"IBM Research"}]},{"given":"Elke A.","family":"Rundensteiner","sequence":"additional","affiliation":[{"name":"Worcester Polytechnic Institute"}]},{"given":"David","family":"Maier","sequence":"additional","affiliation":[{"name":"Portland State University"}]}],"member":"320","published-online":{"date-parts":[[2017,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Esper. http:\/\/www.espertech.com\/.  Esper. http:\/\/www.espertech.com\/."},{"key":"e_1_2_1_2_1","unstructured":"Flink. https:\/\/flink.apache.org\/.  Flink. https:\/\/flink.apache.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Google Dataflow. https:\/\/cloud.google.com\/dataflow\/.  Google Dataflow. https:\/\/cloud.google.com\/dataflow\/."},{"key":"e_1_2_1_4_1","unstructured":"Microsoft StreamInsight. https:\/\/technet.microsoft.com\/en-us\/library\/ee362541%28v=sql.111%29.aspx.  Microsoft StreamInsight. https:\/\/technet.microsoft.com\/en-us\/library\/ee362541%28v=sql.111%29.aspx."},{"key":"e_1_2_1_5_1","unstructured":"Stock data. http:\/\/davis.wpi.edu\/datasets\/Stock_Trace_Data\/.  Stock data. http:\/\/davis.wpi.edu\/datasets\/Stock_Trace_Data\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376634"},{"issue":"1","key":"e_1_2_1_7_1","first-page":"480","article-title":"Linear road: A stream data management benchmark","volume":"30","author":"Arasu A.","year":"2004","journal-title":"PVLDB"},{"issue":"1","key":"e_1_2_1_8_1","first-page":"336","article-title":"Resource sharing in continuous sliding-window aggregates","volume":"30","author":"Arasu A.","year":"2004","journal-title":"PVLDB"},{"key":"e_1_2_1_9_1","first-page":"412","volume-title":"CIDR","author":"Demers A.","year":"2007"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.12"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_12_1","volume-title":"Writers Club Press","author":"Khan A.","year":"2002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142543"},{"issue":"1","key":"e_1_2_1_14_1","first-page":"345","article-title":"AQuery: Query language for ordered data, optimization techniques, and experiments","volume":"29","author":"Lerner A.","year":"2003","journal-title":"PVLDB"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058150.1058158"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066193"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453890"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.95"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989416"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376682"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831367"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559867"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253359"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035947"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"O. Poppe C. Lei E. A. Rundensteiner and D. Maier. GRETA: Graph-based Real-time Event Trend Aggregation. http:\/\/users.wpi.edu\/~opoppe\/papers\/Greta-full.pdf 2017. Technical report in progress.  O. Poppe C. Lei E. A. Rundensteiner and D. Maier. GRETA: Graph-based Real-time Event Trend Aggregation. http:\/\/users.wpi.edu\/~opoppe\/papers\/Greta-full.pdf 2017. Technical report in progress.","DOI":"10.14778\/3151113.3151120"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593684"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005568"},{"key":"e_1_2_1_28_1","volume-title":"U. Sch\u00f6ning. Theoretische Informatik - kurzgefa\u00dft (","year":"1997","edition":"3"},{"issue":"1","key":"e_1_2_1_29_1","first-page":"99","article-title":"SEQ: Design and Implementation of a Sequence Database System","volume":"22","author":"Seshadri P.","year":"1996","journal-title":"PVLDB"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752940"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142520"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593671"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066192"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0180-z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3151113.3151120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:34:43Z","timestamp":1672223683000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3151113.3151120"}},"subtitle":["graph-based real-time event trend aggregation"],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.14778\/3151113.3151120"],"URL":"https:\/\/doi.org\/10.14778\/3151113.3151120","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}