iDB2008

Fukushima • Sept.22, 2008

A RealReal-TimeTime Event Stream
Processing System for RFID
Monitoring Applications
YU Ge
School of Information Science andEngineering
N thNortheasterntUniversity,U iit ChinaChi

O tliOutline| Research Background| ResearchRh IIssues ini Event-Centric
EtC tig
Processing| Overview of the REvent System| Key Techniques| SummaryResearchRh Background
B kd|

RFID (Radio Frequency IDentification)
activetags

passivetag

readerreaderThrough RFID, Billions of objects around world canreport their identies, positions, histories, etc. => Ani tinternett off things![ITUthi![ITU InternetI tt Reports
Rt 2005]

RResearchh Background
B kd| Applications ofRFID

z being applied• logistics management• asset tracking• access control andpersonal tracking• sensor network……
z in future• goods flow
• people flow
• equipment flow
• money flow……

• A huge amount of RFID
data could be generated
continually• need to be processed inreal-time!

RResearchh Background
B kd| Characteristics of RFID dataz Spatio-temporal, dynamics and correlations• Data contains timetime, location
location, and statusz Rich semantics.

• Objects carry a lot of information• related with its context status and background knowledgez Uncertainty and heterogeneity• missing readings, and repeat readings• dirty dataz Streaming,
Stibatchingb t hi andd massive
i volumel• automatically generated rapidly in form of streaming• Objects must be checked in a batch• needs to be processed in real time

RResearchh BackgroundB kd| Current solution for RFID applications
z data-centric systems• Usingg traditional database technology,
gy, e.g.
g active
databases, real-time databases.
z event-centric systems• treat events as first class citizen• perform event processing directly on data source• typical systems: SASE system and Cayuga systemtagged object

readerserverRFID
middle ware

databaseapplications

Research Issues||

CEP (Complex Event Processing)
Four basic approaches of CEP
1.
2.
3.
4.

finite automata based model
Petri-net based model
tree-based model
directed graph based modelResearch Issues| Challenging
z Complex semantics, massive data volume, andinaccurate raw data
¾ to effectively manage RFID data, stream-style processing
mechanisms is neededz Complex constraints• temporal order• numeric value interval¾ traditional ECA rules are not feasible¾ new event model and algebraic operations are neededResearch Issues| Challenging
z Non-spontaneous composite events• negation events• repetition events¾ the occurrence of the constituent event can not lead to theoccurrence of the composite event¾ special query processing algorithms are neededz Many queries registered over the same event

stream¾ new query optimization policy is required

Research Issues| Problems remain to be solved:
z how to process event happening orders of “and”, ”or”

andd ””same titime””
z how to compose composite eventsz how to make use of query sharing for optimizationz how to schedule real-time tasks to meet deadline
z how to deal with uncertain data with probability
z how to perform distributed CEPREvent : high-performance real-time event
stream processing system

OOverview
ioff theth REvent
REt System
S t
RFID event stream

EventCollector

EventQueue

Real-time taskscheduler

Eventnotifier

Event stream
Pre-processor

Event detectionengineEvent mining
engineQueryprocessor

Context
manager

Event-basemanager

Pattern-basemanager

Queryplan

Context-baseEvent-basePattern-base| The architecture of REvent system

OOverviewi
off theth REvent
REt System
S t|

Major modules of REvent systemz

Real-time task scheduler• the proxy of the whole systemz

Query processor• registers queries for event, makes query execution planz

Event pre-processor• cleans raw data and generates basic eventsz

E
Eventt detectiond t ti enginei• filtering and detection of composite events by matching rulesz

Event miningg engineg• summary analysis, temporal association mining, classification
mining, and outlier detection

OOverview
ioff theth REvent
REt SystemS t|

Other auxiliary modules:z

Context manager• provides the information about RFID context and backgroundknowledge.

z

Event-base managerg• provides temporary events and archived historic eventszRule-base manager• provides
id pre-definedd fi d rules
l ffor ddetection
t ti andd storestminingi iposteriori rules.

z

Event collector• gets raw data from RFID readers

OOverview
ioff theth REvent
REt System
S t|

Th basicTheb i data
d t structures
ttz

Event queue• a buffer containing basic eventsz

Query plan
• a buffer containing execution planszContext-base• a database about context and background about thejobserved objectsz

Event-base• a database containing eventszRule-base• a database containing rules

OOverview
ioff theth REvent
REt System
S t|

Semantic event modelz|

Basic event (EId, Etype, TS, Location, OID, Data)E
Eventt operationti algebral b
Sequence operationsz Non-sequence
Non sequence operations: negation and repetitionz Restriction operations: partition, within, continunity.
z Complex
poperations
p: sliding-window,g, groupingg p g andstatistics.
z|Query language
Express complex rules and application logics
z XML based script languagez SQL like event query languagezO
Overviewi
off theth REvent
REt System
S tz Examples of CEP operations

K TKeyTechniquesh i| Grouping based data cleaning(1)z Cleaning
Cli aimiReaderat door

• False negative: missing in 30% probability• False positive: wrong readings
readings, repetitionz Basic idea

• Grouping objects according to their association• Clean data according to the information within agroup

Visitorwith tag

K TKeyTechniquesh i| Pre-processingz DataD t cleaningli

9Grouping based data cleaning strategy| Real time query processingz Pattern matchingz Real time scheduling

9Deadline-sensitive ppattern matchingg

K TKeyTechniquesh i| Grouping based data cleaning(2)z GroupGidentification
id tifi ti problemsbl• Interferences of different groups• Changes of groupgro p memberships

K TKeyTechniquesh i| Grouping based data cleaning(3)z Association degreez Graph based association modelz Compressed tree modelz List modelz spliting and re-grouping algorithm

K T
KeyTechniquesh i| Grouping based data cleaning(4)

K T
Key
Techniquesh i| Grouping based data cleaning(5)K T
KeyTechniquesh i| Deadline-sensitive pattern matching(1)z AimAi• more correct results that meet deadline
z Basic idea
• Statistics based approach• RFID ddatat arrival
i l modeld l• Event processing model• DeadDead-line
line meeting model• Resource allocation model

K T
KeyTechniquesh iDeadline-sensitive pattern matching(2)z Possion
Pi didistribution
t ib ti b
based
d arrival
i l modeld lz NFA bbased
d processing
i modeld lK TKeyTechniquesh i| Deadline-sensitive pattern matching(3)z Processing
Pi moded b
based
d costt modeld lPattern
Unrestricted ModeFirst Mode
Recent Mode
Chronicle Mode
Cumulative Mode
Continuous Mode

Query results of SEQ(E1,E2,E3) withCost of other subevents

Extra cost forterminating event

K T
KeyTechniquesh i| Deadline-sensitive pattern matching(4)z Deadline
D dli meetingti modeld lz Minimum resource modelK TKeyTechniquesh i| Deadline-sensitive pattern matching(5)z Disorder
Di d modeld lz Least-disorder based scheduling strategy

K TKeyTechniquesh i| Deadline-sensitive pattern matching(5)z Simulation experimental results

Summaryz Analyzing the characteristics of RFID event

streamz Exploring the challenging problems and keytechniques• RFID event modeling, data cleaning, event detection,
event mining, query optimization, real-time taskscheduling, and system architecturez Designing a high performance real-time event

stream pprocessingg systemySummaryz Future works• Prototype implementation and performance
evaluation• Scenario Simulator by Netlog• Real data set collected by experimental devices• Practical applications• Product location and tracking
eop e ttracking
ac g in pub
publiccaarea
ea likee museums,
useu s, paparkss• People

The EndTh k ！
Thanks！