ZStream : a cost-based query processor for composite event detection

Composite (or Complex) event processing (CEP) systems search sequences of incoming primitive events for occurrences of user-specified event patterns. Recently, they are gaining more and more attention in a variety of areas due to their powerful and expressive query language and performance potential. Sequentiality (temporal ordering) is the primary way in which CEP relates events to each other. Examples include tracing a car's movement in a predefined area (where a car moves through a series of places), detecting anomalies in stock prices (where the rise and fall of the price of some stocks is monitored), detecting intrusion in network monitoring (where a specific sequence of malicious activities is detected) or catching break points in debugging systems (where a sequence of function calls are made). But even searching for a simple sequence pattern involving only equality constraints between its components is an NP-complete problem. Furthermore, simple sequentiality is not enough to express many real world patterns, which also involve conjunction (e.g., concurrent events), disjunction (e.g., a choice between two options) and negation, making the matching problem even more complex. In this thesis, we present a CEP system called ZStream to efficiently process such sequential patterns. Besides simple sequentiality, ZStream is also able to support other relations such as conjunction, disjunction, negation and Kleene Closure. ZStream uses a tree-based plan for both the logical and physical representation of query patterns. Using this tree-based infrastructure, ZStream is able to unify the evaluation of sequence, conjunction, disjunction, negation, and Kleene Closure as variants of the join operator. A single pattern may have several equivalent physical tree plans, with different evaluation costs. Hence a cost model is proposed to estimate the computation cost of a plan.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Mei, Yuan, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Samuel Madden.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/44736

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/44736