BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210808T235336Z
LOCATION:Room C
DTSTART;TZID=America/Chicago:20210812T110000
DTEND;TZID=America/Chicago:20210812T111500
UID:icpp_ICPP 2021_sess119_pap488@linklings.com
SUMMARY:Efficient Complete Event Trend Detection over High-Velocity Stream
s
DESCRIPTION:Conference Paper\n\nEfficient Complete Event Trend Detection o
ver High-Velocity Streams\n\nMei, Chen, Jin, Hua, Zhou\n\n\emph{Complete E
vent Trend} (CET) detection over large-scale event streams is important an
d challenging in various applications such as financial services, real-tim
e business analysis, and supply chain management. A potential large number
of partial intermediate results during complex event matching can raise p
rohibitively high memory cost for the processing system. The state-of-the-
art scheme leverages compact graph encoding, which represents the common s
ub-sequences of different complex events using a common sub-graph to achie
ve space efficiency for storing the intermediate results. However, we show
that such a design raises unacceptable computation cost for the graph tra
versal needed whenever a new event comes. To address this problem, in this
paper, we propose a novel \emph{attribute-based indexing} (ABI) graph mod
el to represent the relationship between events. By classifying the predic
ates and constructing the graph based on both the comparators in the predi
cates and the attribute values of the events, we achieve parallel event st
ream processing and efficient graph construction. Our design significantly
reduces the total computation cost of graph construction from $O(n^2)$ to
$O(nlog(m))$, where $n$ is the number of events and $m$ is the number of
the attribute vertices. We further design several efficient traversal-base
d algorithms to extract CETs from the graph. We implement our design and c
onduct comprehensive experiments to evaluate the performance of this desig
n. The results show that our design wins a couple of orders of magnitude b
ack from state-of-the-art schemes.
END:VEVENT
END:VCALENDAR