ZStream : a cost-based query processor for composite event detection
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/44736 |
| _version_ | 1826214714417348608 |
|---|---|
| author | Mei, Yuan, Ph. D. Massachusetts Institute of Technology |
| author2 | Samuel Madden. |
| author_facet | Samuel Madden. Mei, Yuan, Ph. D. Massachusetts Institute of Technology |
| author_sort | Mei, Yuan, Ph. D. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T16:10:19Z |
| format | Thesis |
| id | mit-1721.1/44736 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:10:19Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/447362019-04-11T14:26:55Z ZStream : a cost-based query processor for composite event detection Searching for optimal plans in sequential composite event detection Mei, Yuan, Ph. D. Massachusetts Institute of Technology Samuel Madden. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. Includes bibliographical references (p. 103-104). 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. (cont.) Experiments show that our cost model can capture the real evaluation cost of a query plan accurately. Based on this cost model and using a simple set of statistics about operator selectivity and data rates, ZStream is able to adjust the order in which it detects patterns. In addition, we design a dynamic programming algorithm and propose equivalent transition rules to automatically search for an optimal query plan for a given pattern. by Yuan Mei. S.M. 2009-03-16T19:36:13Z 2009-03-16T19:36:13Z 2008 2008 Thesis http://hdl.handle.net/1721.1/44736 298258226 eng 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. http://dspace.mit.edu/handle/1721.1/7582 105 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Mei, Yuan, Ph. D. Massachusetts Institute of Technology ZStream : a cost-based query processor for composite event detection |
| title | ZStream : a cost-based query processor for composite event detection |
| title_full | ZStream : a cost-based query processor for composite event detection |
| title_fullStr | ZStream : a cost-based query processor for composite event detection |
| title_full_unstemmed | ZStream : a cost-based query processor for composite event detection |
| title_short | ZStream : a cost-based query processor for composite event detection |
| title_sort | zstream a cost based query processor for composite event detection |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/44736 |
| work_keys_str_mv | AT meiyuanphdmassachusettsinstituteoftechnology zstreamacostbasedqueryprocessorforcompositeeventdetection AT meiyuanphdmassachusettsinstituteoftechnology searchingforoptimalplansinsequentialcompositeeventdetection |