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

Figure 4.1. An NFA structure and PAIS for sequence Q3.

and value constraint evaluation during the process of complex event de-
tection. For example, Figure 4.1 shows the NFA structure and the PAIS
for Query Q 3 (SEQ(A, B, D)) .
( SEQ(A, B, D) ) is illustrated in Figure4.1 .
A SASE extended model which combines a finite automaton with
versioned match buffers is proposed in [70] to support event backtracking
and value constraint evaluation during complex RFID event detection
and general pattern matching.
Traditional tree based event detection modes take an bottom-up ap-
proach (e.g., Snoop [72]), which is inapplicable to detecting RFID events.
Many temporal constrained RFID events such as those generated from
SEQ + and NOT constructors are non-spontaneous and can never be trig-
gered by the bottom-up approach. As summarized in [73, 74], there are
three event detection modes such as Pull ( ↑ ), Push( ↓ )andMixed( )

generalized in the RCEDA framework.
RCEDA model [73, 74] extends tree-based detection model for tempo-
ral constraints handling. Fundamental event constructors form basic tree
operators ( Figure4.2 ) , and complex events can be represented by com-
bining these tree operators to form more complex tree based representa-
tions. For example, Figure 4.3b illustrates the graphical representation
of a complex event E = WITHIN(TSEQ + (E1 ∨ E2, 0.1sec, 1sec) ; E3,

10min) after interval propagating from Figure 4.2 . We use vE.within
to represent the interval constraint on event E . To support both pull
and push modes, RCEDA provides two way detections through the tree
model: bottom-up event propagation through the tree to trigger parent
events, and top-down event querying to support the detection of non-
spontaneous events. The detection of non-spontaneous events is sup-
ported through the introduction of “ pseudo-events ”. A pseudo event