A model for continuous query latencies in data streams

In this paper we propose a formal model for characterizing latencies affecting the computation of a continuous query either in a Data Stream Management System (DSMS) or in a Complex Event Processing (CEP) system. In the model, a query can be thought of as constructed out of basic Event Processing Units (EPUs) interconnected among themselves. EPUs are modeled considering just few parameters, used to define the EPU processing logic. In order to model the continuous query we use an acyclic directed (data-ow) graph whose nodes are the EPUs and edges represent the ow of information (events) processed by the EPUs themselves. The outcome of this model is to associate with each data- ow graph a set of latency metrics, namely reactivity, activity, and output latencies, and a complexity measure - that we call data-ow graph complexity - representing the input dimension required to produce an output event. The proposed model can be used to compare and contrast different data-ow graphs in order to assess their latency metrics. This is a crucial step in selecting one of such graphs that meets at best the latency requirements imposed by the programmer before its actual submission to a DSMS or to a CEP system. Furthermore, the model can be considered an effective mean through which formally comparing data- ow graphs and predicting their behavior before an actual experimental validation phase. Copyright 2011 ACM.