Stream Data Processing
by Chakravarthy, Sharma; Jiang, Qing ChunFormat: Hardcover
Pub. Date: 2009-04-24
Publisher(s): Springer Verlag
Other versions by this Author
List Price: $209.99
Rent Textbook
Select for Price
Rent Digital
$124.02*
New Textbook
We're Sorry
Sold Out
Used Textbook
We're Sorry
Sold Out
How Marketplace Works:
- This item is offered by an independent seller and not shipped from our warehouse
- Item details like edition and cover design may differ from our description; see seller's comments before ordering.
- Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
- Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
- Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.
Summary
Traditional database management systems, widely used today, are not well-suited for a class of emerging applications, such as computer network management, homeland security, sensor computing, and environmental monitoring. These applications need to continuously process large amounts of data coming in the form of a stream, and meet stringent response time requirements. Support for handling QoS metrics, such as response time, memory usage, and throughput, is central to any system proposed for the above applications.Stream Data Processing: A Quality of Service Perspective (Modeling, Scheduling, Load Shedding, and Complex Event Processing), presents a new paradigm suitable for stream and complex event processing. This book covers a broad range of topics in stream data processing and includes detailed technical discussions of a number of proposed techniques.This volume is intended as a textbook for graduate courses and as a reference book for researchers, advanced-level students in CS, and IT practitioners.
Author Biography
Sharma Chakravarthy is professor of Computer Science and Engineering at the University of Texas at Arlington (UTA) since 2000. He was at the University of Florida, Gainesville earlier, and was a member of the technical staff at Computer Corporation of America (CCA) and Xerox Advanced Information Technology group. His 25+ years of experience in industry, research laboratories, and academia gives him a unique perspective which is a healthy blend of theory, systems-orientation, and applicability of solutions to real-world problems. This book elaborates on two important areas in Computer Science, namely, stream data processing and complex event processing highlighting their synergy. This book is the result of many years of research and development in these two areas by the author. Qingchun Jiang is a Principal Member of Technical Staff at Oracle USA. He currently works on Oracle Times Ten In-Memory database system. His primary research and development interests include SQL query processing and optimization, data stream processing, and software architecture design and analysis. He holds a Ph.D in Computer Science from the University of Texas at Arlington.
Table of Contents
| List of Figures | p. XIX |
| List of Tables | p. XXIII |
| List of Algorithms | p. XXV |
| Introduction | p. 1 |
| Paradigm Shift | p. 3 |
| Data Stream Applications | p. 5 |
| Book Organization | p. 6 |
| Overview of Data Stream Processing | p. 9 |
| Data Stream Characteristics | p. 9 |
| Data Stream Application Characteristics | p. 10 |
| Continuous Queries | p. 12 |
| Window Specification | p. 14 |
| Examples of Continuous Queries | p. 16 |
| QoS Metrics | p. 18 |
| Data Stream Management System Architecture | p. 19 |
| Summary of Chapter 2 | p. 20 |
| DSMS Challenges | p. 23 |
| QoS-Related Challenges | p. 23 |
| Capacity Planning and QoS Verification | p. 23 |
| Scheduling Strategies for CQs | p. 24 |
| Load Shedding and Run-Time Optimization | p. 25 |
| Complex Event and Rule Processing | p. 26 |
| Design and Implementation of a DSMS with CEP | p. 27 |
| Concise Overview of Book Chapters | p. 27 |
| Literature Review | p. 27 |
| Continuous Query Modeling | p. 28 |
| Scheduling Strategies for CQs | p. 28 |
| Load Shedding in a DSMS | p. 29 |
| NFMi: A Motivating Application | p. 30 |
| DSMS and Complex Event Processing | p. 30 |
| Design and Implementation of Prototypes | p. 31 |
| Literature Review | p. 33 |
| Data Stream Management Systems | p. 33 |
| Aurora and Borealis | p. 33 |
| Stream | p. 34 |
| TelegraphCQ | p. 35 |
| MavStream | p. 36 |
| Others | p. 37 |
| QoS-Related Issues | p. 38 |
| Continuous Query Modeling for Capacity Planning | p. 38 |
| Scheduling Strategies for CQs | p. 39 |
| Load Shedding in a DSMS | p. 40 |
| Design and Implementation of Prototypes | p. 41 |
| Complex Event Processing | p. 41 |
| Mid- to Late-Eighties: Active Databases | p. 41 |
| Nineties: Active Object-Oriented Databases | p. 42 |
| Beyond 2000: (Distributed) Complex Event Processing | p. 45 |
| Commercial and Open Source Stream and CEP Systems | p. 47 |
| Modeling Continuous Queries Over Data Streams | p. 49 |
| Continuous Query Processing | p. 50 |
| Operator Path | p. 50 |
| Operator Modeling | p. 52 |
| Scheduling and Service Discipline | p. 53 |
| Problem Definition | p. 54 |
| Notations and Assumptions | p. 56 |
| Stability and Performance Metrics | p. 57 |
| Modeling Relational Operators | p. 57 |
| Modeling Select and Project Operators | p. 58 |
| Modeling Window-Based Symmetric Hash join | p. 60 |
| Steady State Processing Cost | p. 60 |
| Handling Bursty Inputs and Disk-Resident Data | p. 68 |
| Modeling Continuous Queries | p. 69 |
| Modeling Operators with External Input(s) | p. 71 |
| Modeling Operators with Internal Input(s) | p. 75 |
| Modeling Operators with External and Internal Inputs | p. 79 |
| Scheduling Strategy and Vacation Period | p. 79 |
| Computing Memory Usage and Tuple Latency | p. 82 |
| Intuitive Observations | p. 82 |
| Tuple Latency | p. 82 |
| Service Discipline | p. 82 |
| Scheduling Algorithms | p. 83 |
| Choice of Query Plans | p. 84 |
| Input Rate | p. 84 |
| Experimental Validation | p. 85 |
| Validation of Operator Models | p. 86 |
| Validation of Continuous Query Plan Models | p. 89 |
| Summary of Chapter 5 | p. 93 |
| Scheduling Strategies For CQs | p. 95 |
| Scheduling Model and Terminology | p. 96 |
| Scheduling Model | p. 97 |
| Notations | p. 99 |
| Impact of Scheduling Strategies on QoS | p. 103 |
| Novel Scheduling Strategies for CQs | p. 105 |
| Path Capacity Strategy | p. 106 |
| Analysis of CQ Scheduling Strategies | p. 108 |
| Segment Strategy and Its Variants | p. 111 |
| Hybrid Threshold Scheduling Strategy | p. 122 |
| CQ Plan Characteristics | p. 124 |
| Starvation-Free Scheduling | p. 125 |
| Experimental Validation | p. 126 |
| Setup | p. 126 |
| Evaluation of Scheduling Strategies | p. 127 |
| Summary of Chapter 6 | p. 136 |
| Load Shedding In Data Stream Management Systems | p. 137 |
| The Load Shedding Problem | p. 138 |
| Integrating Load Shedders | p. 140 |
| Load Shedder as Part of a Buffer | p. 142 |
| Types of Load Shedders | p. 143 |
| Load Shedding Framework | p. 143 |
| Prediction of Query Processing Congestion | p. 144 |
| Placement of Load Shedders | p. 151 |
| Allocation of Load for Shedding | p. 156 |
| Load Shedding Overhead | p. 157 |
| Experimental Validation | p. 158 |
| Prototype Implementation | p. 158 |
| Experiment Setup | p. 158 |
| Load Shedding with Path capacity strategy | p. 160 |
| Load Shedding with EDF scheduling strategy | p. 163 |
| Summary of Chapter 7 | p. 165 |
| NFMi: An Inter-Domain Network Fault Management System | p. 167 |
| Network Fault Management Problem | p. 168 |
| Data Processing Challenges for Fault Management | p. 170 |
| Semi-structured Text Messages | p. 171 |
| Large Number of Messages | p. 172 |
| Complex Data Processing | p. 172 |
| Online Processing and Response Time | p. 172 |
| Stream- and Event-Based NFMi Architecture | p. 173 |
| Message Splitter | p. 175 |
| Message Filter and Information Extractor | p. 175 |
| Alarm Processing | p. 178 |
| Three-Phase Processing Model for NFMi | p. 178 |
| Continuous Query (CQ) Processing Phase | p. 178 |
| Complex Event Processing Phase | p. 181 |
| Rule Processing Phase | p. 182 |
| Summary | p. 183 |
| Transactional Needs of Network Management Applications | p. 184 |
| Updates and Views | p. 185 |
| Summary of Chapter 8 | p. 186 |
| Integrating Stream And Complex Event Processing | p. 187 |
| Motivation | p. 188 |
| Event Processing Model | p. 191 |
| Event Detection Graphs | p. 192 |
| Event Consumption Modes | p. 192 |
| Event Detection and Rule Execution | p. 194 |
| Complex Event Vs. Stream Processing | p. 195 |
| Inputs and Outputs | p. 195 |
| Consumption Modes Vs. Window Types | p. 196 |
| Event Operators Vs. CQ Operators | p. 197 |
| Best-Effort Vs. QoS | p. 197 |
| Optimization and Scheduling | p. 198 |
| Buffer Management and Load Shedding | p. 198 |
| Rule Execution Semantics | p. 199 |
| Summary | p. 199 |
| MavEStream: An Integrated Architecture | p. 200 |
| Strengths of the Architecture | p. 201 |
| Stream-Side Extensions | p. 203 |
| Named Continuous Queries | p. 203 |
| Stream Modifiers | p. 205 |
| Event-Side Extensions | p. 207 |
| Generalization of Event Specification | p. 207 |
| Event Specification using Extended SQL | p. 208 |
| Mask Optimization | p. 210 |
| Enhanced Event Consumption Modes | p. 210 |
| Rule Processing | p. 211 |
| Summary of Chapter 9 | p. 213 |
| MavStream: Development of a DSMS Prototype | p. 215 |
| MavStream Architecture | p. 216 |
| Functionality | p. 216 |
| MavStream Server Design | p. 217 |
| MavStream Server Implementation | p. 219 |
| Window Types | p. 220 |
| Functionality | p. 220 |
| Design | p. 220 |
| Implementation | p. 222 |
| Stream Operators and CQs | p. 222 |
| Functionality | p. 222 |
| Design of Operators | p. 223 |
| Implementation | p. 225 |
| Buffers and Archiving | p. 229 |
| Functionality | p. 229 |
| Buffer Manager Design | p. 230 |
| Buffer Manager Implementation | p. 231 |
| Run-time Optimizer | p. 231 |
| Functionality | p. 231 |
| Run-time Optimizer Design | p. 232 |
| Run-time Optimizer Implementation | p. 234 |
| QoS-Delivery Mechanisms | p. 243 |
| Functionality | p. 243 |
| Scheduler Design | p. 243 |
| Scheduler Implementation | p. 245 |
| Load Shedder Design | p. 246 |
| Load Shedder Implementation | p. 246 |
| System Evaluation | p. 248 |
| Single QoS Measure Violation | p. 248 |
| Multiple QoS Measures Violation | p. 249 |
| Effect of Load Shedding on QoS Measures | p. 253 |
| Effect of Load Shedding on Error in Results | p. 257 |
| Integrating Cep With a DSMS | p. 261 |
| MavEStream: Integration Issues | p. 262 |
| Event Generation | p. 263 |
| Continuous Event Query (CEQ) Specification | p. 264 |
| Events and Masks | p. 264 |
| Address Space Issues | p. 265 |
| Summary | p. 265 |
| Design of the Integrated System | p. 266 |
| Address Space | p. 266 |
| Continuous Event Queries | p. 266 |
| Events and Masks | p. 268 |
| Event Generator Interface | p. 271 |
| Need for a Common Buffer for All Events | p. 272 |
| Complex Events and Rule Management | p. 274 |
| Implementation Details of Integration | p. 275 |
| Input Processor | p. 276 |
| Event and Rule Instantiator | p. 278 |
| Event Generator Interface | p. 278 |
| Stream Modifiers | p. 281 |
| Tuple-Based Stream Modifiers | p. 281 |
| Window-Based Stream Modifiers | p. 282 |
| Implementation | p. 282 |
| Additional Benefits of CEP Integration | p. 284 |
| Summary of Chapter 11 | p. 285 |
| Conclusions And Future Directions | p. 287 |
| Looking Ahead | p. 287 |
| Stream Processing | p. 288 |
| Continuous Query Modeling | p. 289 |
| Scheduling | p. 289 |
| Load Shedding | p. 290 |
| Integration of Stream and Event Processing | p. 291 |
| Epilogue | p. 293 |
| References | p. 295 |
| Index | p. 315 |
| Table of Contents provided by Ingram. All Rights Reserved. |
An electronic version of this book is available through VitalSource.
This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.
By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.
Digital License
You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.
More details can be found here.
A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.
Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.
Please view the compatibility matrix prior to purchase.