EVENT PROCESSING IN SENSOR STREAMS - Managing and Mining Sensor Data - page 94

be processed in arbitrary ways within an event flow processing system
by storing those tuples and retrieving as needed to match desired pat-
terns. Most current research assumes events are ordered, and do not
consider the concurrence and overlapping of events. However, in many
real applications this assumption may not be valid.
Meanwhile, the real-time processing in temporal orders of event streams
generated from distributed devices is a primary challenge for today's
monitoring and tracking applications. In pervasive computing environ-
ments, event sequences might be out-of-order at the processing engine
due to machine failure or network latency. Most systems [44, 45], either
event-based or stream-based, assume a total ordering among event ar-
rivals. Such existing technologies are likely to fail in such circumstances,
either missing correct matches (i.e., false negatives) or producing incor-
rect matches (i.e., false positives). Supporting both in-order as well as
out-of-order events eciently and in real-time is an important research
topic for complex event detection.
Based on the summary of different scenarios, the existing work on
event disorder can be categorized into two types, one focusing on real
time where the output is unordered, and another one focusing on the
correctness where the output is ordered. If the input event stream to the
query engine is unordered, it is reasonable to produce unordered output
events. The method in [46] permits unordered sequence output based
on an aggressive strategy. The aggressive strategy produces maximal
output under the assumption that out-of-order event arrival is rare. In
the case when out-of-order data arrival occurs, the results that have
already been erroneously output will be corrected. One requirement here
is that, for traditionally append-only streams, data cannot be updated
once it is placed on a stream. Thus, a traditional append-only event
model is no longer adequate. Another requirement is that, to enable the
correction at any time, the access to historical operator states are needed
until safe purging is possible. The upper bounds of K-slack could be used
for periodic safe purging of the states of WinSeq and WinNeg operators
when event instances are out of Window size K. This ensures that data
are preserved so that any prior computation can be re-computed from
its original input as needed. The approach extends the common append-
only stream model to support the correction of prior released data on a
stream. Two types of stream messages are used: Insertion tuple < + ,t>
is induced by an out-of-order positive event, where t is a new sequence
result. Deletion tuple < ,t > is induced by an out-of-order negative

event, such that t consists of the previously processed sequence. Deletion
tuples cancel previous sequence results through the appearance of an

−