An optimistic approach to handle out-of-order events within analytical stream processing Igor E. Kuralenok #1 , Nikita Marshalkin #2 , Artem Trofimov #3 , Boris Novikov #4 # JetBrains Research Saint Petersburg, Russia 1 ikuralenok@gmail.com 2 marnikitta@gmail.com 3 trofimov9artem@gmail.com 4 borisnov@acm.org Abstract—In recent years, there has been a growth in research and industrial solutions in the field of distributed stream pro- cessing. However, even state-of-the-art stream processing systems experience difficulties with out-of-order data arrival. The most common solution to this issue is buffering. Its main problem is the extra cost for blocking before each order-sensitive operation. The goal of this paper is to propose and evaluate an optimistic approach to handle out-of-order events. We introduce a method that is suitable for any stateful operation and needs a single buffer for the complete computational pipeline. Such technique requires extra network transfers and re-computations, but the experiments demonstrate that a prototype of our approach is able to create low overhead while ensuring the correct ordering. I. I NTRODUCTION Nowadays, a lot of real-life applications use stream pro- cessing for network monitoring, financial analytics, training machine learning models, etc. State-of-the-art industrial stream processing systems, such as Flink [1], Samza [2], Storm [3], Fig. 1. An example of common distributed stream processing pipeline that Heron [4], are able to provide low-latency and high-throughput breaks the input order of operation in distributed environment for this kind of problems. How- ever, providers of the order-sensitive computations remain suboptimal. Most of these systems assume that events are the business-logic, which can lead to the maintenance cost fed to the system with monotonically increasing timestamps increase and is error-prone. or with minor inversions. Often, such timestamps can be assigned at system’s entry. Nevertheless, even if input items In this paper we introduce an optimistic approach to handle arrive monotonically, they can be reordered because of the out-of-order items. Our evaluation demonstrates the low over- subsequent parallel and asynchronous processing. In this case, head of our method. The contributions of this paper are the order-sensitive operations located deeper in data flow pipeline following: can be broken. Figure 1 shows the example of common • Definition of new optimistic technique to handle out- distributed stream processing pipeline that breaks the input of-order items in stateful operations that requires single order of the operation 2, even if inputs are monotonic and buffer per computational pipeline links between operations guarantee FIFO order. • Analysis of properties of this approach The typical way to achieve in-order processing is to set • Demonstration of working example that applies proposed up a special buffer in front of operation. This buffer collects method all input items until some user-provided condition is satisfied. Then the contents of the buffer are sorted and fed to the The rest of the paper is structured as follows: in section II operation. The main disadvantage of such technique is latency we formalize the preliminaries of stream processing, the growth. This issue becomes even more significant if the examples of tasks that require ordered input are described in processing pipeline contains several operations that require section III, the typical approaches for handling out-of-order ordered input. The problem here is that each buffer increases events are discussed in IV, our optimistic technique is detailed latency, because of the additional waiting time. in V and its performance is demonstrated in VI, the main The alternative is to develop business logic tolerant to out- differences between proposed method and existing ones are of-order items. However, this approach is suitable only for a shown in VII, finally we discuss the results and our plans limited set of tasks. Moreover, it may dramatically complicate in VIII. 22 II. S TREAM PROCESSING CONCEPTS D. Physical deployment In this section we define some preliminaries for distributed As mentioned above, each operation can be partitioned stream processing. It allows us to unify required terms and between multiple computational units. Data items can be to introduce definitions, which are needed for the subsequent balanced between partitions by key extracted from an item’s statements. payload for stateful operations. For stateless operations items can be balanced randomly. The schema of physical partitioning In this paper a stream processing system is considered as of operations is sometimes called physical graph. Regarding a shared-nothing distributed runtime. It handles input items physical links between operations, in the most cases, it is and processes them one-by-one according to user-provided assumed that they guarantee FIFO order. logic. It is able to handle a potentially unlimited number of items. The main requirement of this kind of data processing E. Guarantees systems is to provide low latency between event occurrence and its processing under a fixed load. The term distributed Recognized important property of stream processing sys- implies that user’s procedures can be partitioned into distinct tems is the type of guarantees it provides in case of failures. computational units or shards. The following subsections detail There are three main types of such guarantees. At most once the properties of such systems more precisely. semantics states that each input event is processed once or not processed at all. At least once guarantees that each input item is processed, but possibly multiple times, that can lead to A. Data flow result duplication. Exactly once semantics guarantee that each The basic data flow abstraction is a stream. The stream input event is processed exactly one time. is an infinite sequence of heterogeneous data items. Each data item contains a payload defined by a user. Besides, it III. TASKS THAT REQUIRE IN - ORDER INPUT can be accompanied by meta-information. Typically, meta- In this section we outline common problems that require information is used to define an order on data items. For the order persistence of input items and describe a couple of instance, it can be represented as a UNIX timestamp in computation scenarios, which can be found in many real-life milliseconds. projects. B. Computation flow A. Tasks requiring complete event retrieval Commonly, the computational pipeline is defined in the The processing of the single event could be split into form of logical graph. The vertices of the logical graph are multiple independent parts that are executed in parallel. After operations, and the edges are links between them. Logical execution finishes, the results must be combined into a single graph defines only relations between operations, but it does cumulative item. This task could be naturally implemented not describe the physical deployment. The logical graph for using order guarantees: the final part of the task could be the pipeline shown in Figure 1 is presented in Figure 2 flagged and receiving the flagged result guarantees that the rest of the operation is completed. Unfortunately, as it was shown in Figure 1, independent processing via different paths can lead to reordering. As an example, we can mention the computation of inverted index. Pipeline shown in Figure 1 can be applied for the task. In this case, operation 1 accepts documents from the input and Fig. 2. The logical graph for the physical graph shown above for each word produces corresponding positions. Operation 2 receives pairs of word and positions and computes changelog of the inverted index for each word. In order to produce changes for each document in the form of single update, there C. Operations is a need for retrieval all changelogs regarding the document. There are two main types of streaming operations: stateless B. Tasks that depend on the order of input events and stateful. Stateless operations do not need any knowledge about past inputs to process current one correctly. A simple This class includes all non-commutative operations. Such illustration is a map operation that multiplies by two any tasks strictly require the order of input items, because there numeric input item’s payload. On the other hand, stateful are no any other methods to compute a valid result. operations are able to keep some aggregations or summaries Generally, this class of examples includes all windowed of received events. In such case, the output of the operation aggregations. Moving average calculation over a numerical depends not only on the input but also on its current state. As stream is a typical case. Even if values inside window could an example, one can define an operation that sums all previous be arbitrary reordered, the order between windows is required items with numerical payloads. to ensure that incomplete windows are not produced. 23 IV. E XISTING SOLUTIONS There are two most common methods that are used to implement order-sensitive operators: in-order processing (IOP) [5], [6], [7] and out-of-order processing (OOP) [8]. A. In-order processing According to IOP approach, each operation must enforce the total order on output elements that can be violated due Fig. 4. OOP sliding window, range=3, slide=1. Operation must block lower to asynchronous nature of execution. Buffering is usually window until next punctuation arrival used to fulfill this requirement. Figure 3 shows the union operation that combines multiple streams into the single one. Both input streams are ordered, as predecessors must meet V. O PTIMISTIC APPROACH ordering constraint. Nevertheless, if there is arrival time skew The main idea of our method is to represent stateful trans- between input streams, the union must buffer the earlier stream formations as a sequence of a map and windowed grouping to produce ordered output. It is known that IOP is memory operations and handle out-of-order items within them. demanding and has unpredictable latencies and limited scala- Following our approach, we make some assumptions about bility [8]. stream processing system, that is suitable for applying it. Such system must support meta-information on data items, allow cycles in the logical graph, and its set of predefined operations must be sufficient to express map and windowed grouping operations. Additionally, OOP indicators should be supported. The ordering model of data items is defined at the beginning of this section. Then, we show that any stateful transformation can be implemented using the combination of windowed grouping and map operations. After that, we demonstrate an optimistic approach to handle out-of-order items within these Fig. 3. IOP union operation. Due to delay of the upper stream operation operations. At the end of the section, the limitations of such must buffer elements technique are discussed. A. Ordering model B. Out-of-order processing We assume that there is a total order on data items. OOP is an approach that does not require order maintenance If there are multiple data sources and there is no natural if it is not needed. In the case of ordering requirements, OOP ordering between them, the source id can be used in addition buffers input items until a special condition is satisfied. This to the locally assigned timestamp. The items are compared condition is supported by progress indicators such as punctu- lexicographically: timestamps first, then source id. Ordering ations [9], low watermarks [10], or heartbeats [11]. They go is preserved when an item is going through the operations. along the stream as ordinal items, but do not trigger business- More precisely, the order of output items is the same as the logic of the operations. Each progress indicator carries meta- order of corresponding input items. If more than one item information and promises that there are no any elements is generated, they are inserted in output stream sequentially. with lesser meta-information. Therefore, indicators must be Moreover, the output follows corresponding input but precedes monotonic, but data items between two consecutive indicators the next item. The ordering model is shown in Figure 5. F (x) can be arbitrarily reordered. Data sources periodically yield is an arbitrary transformation. Replication and union are used them. to inject original unmodified items into the resulting stream to A timed window operation can be mentioned as an example show the order between items. of OOP approach. A window operation buffers partial results until a progress indicator arrives. After that, the window B. Semantics of map and windowed grouping operations flushes corresponding buffers and propagates the indicator to 1) Map: Map transforms input item into a sequence of the next operation down the stream. its derivatives, according to a user-provided function f . This OOP addresses the downsides of IOP, but the direct imple- sequence can consist of any number of items or even be empty. mentation has flaws too. Even if the input stream is totally 2) Windowed grouping: Windowed grouping is a stateful ordered, the operation must wait for the progress indicator. operation with a numeric parameter window. It is supposed Figure 4 illustrates such case. Bottom window is complete that payloads of input items of grouping operation have key- but must be blocked until the indicator for the item 11 arrives. value form. The state of this operation is represented by a set Another issue of OOP is that periodical flushes can result in of buckets, one for each key. load bursts and an increase in latency. Windowed grouping has the following semantics: 24 • When the state item arrives at grouping, it is inserted in the tail of the corresponding bucket after the item that triggers state updating. The ordering model guarantees that the state item would be processed before the next item. Grouping outputs tuple with this item and the state. However, combine map filters out such tuple, because its last element is the state. This fact implies that the state has been already combined with the first item in the tuple. • When new regular input item arrives at windowed group- ing, it is inserted into the corresponding bucket’s tail, Fig. 5. Ordering model because of the order assumptions. Additionally, the right ordering guarantees that input item is grouped into the tuple with previously generated state item. The next map • Each input item is appended to the corresponding bucket operation combines new item and previous state into the • The output of grouping operation is a window-sized tuple new state item. After that, the new state item is returned of the last items in the corresponding bucket. If bucket to the grouping through the cycle. As in the first case, size is less than window, the output contains full bucket combined map can generate some additional output. The pseudocode is presented in Algorithm 1. Emit function is called to send new items downstream. Algorithm 1 Grouping semantics 1: function I NSERT(item, bucket) 2: A PPEND(bucket, item) 3: lef t ← max(0, bucketlength − window) 4: right ← bucketlength 5: E MIT(new DataItem(bucket[lef t, right])) 6: end function The following example illustrates the semantics of the Fig. 6. The part of the logical pipeline for stateful transformation windowed grouping operation. In this example, payloads of input items are represented as natural numbers: 1, 2, 3, etc. The The example of square matrix multiplication within pro- hash function returns 1 if the number is even and 0 otherwise. posed approach is shown in Figure 7. In this example, input If the window is set to 3, the output is: items are represented as key-value pairs, where the key is the dimension of a matrix, and the value is the matrix itself. The reaction on three input matrices are the following: (1), (2), (1|3), (2|4), (1|3|5), (2|4|6), (3|5|7), (4|6|8)... • When the first matrix A arrives at grouping, it is put The special case of grouping with window = 2 in con- into the empty bucket for 3x3 matrices. After that, the junction with a stateless map is used to implement arbitrary single-element tuple with matrix A is sent to combine map stateful transformation. operation. Combine map creates state object for matrix A, which is just A itself. In the last step, state item is sent C. Stateful transformations using defined operations back to grouping, and it is inserted right after item for matrix A Figure 6 shows the part of the logical pipeline, that can • Matrix B is arrived and inserted into the bucket right be used for stateful transformation. The input of windowed after state item. The tuple containing state item and item grouping operation is supposed to be ordered. There are for matrix B is sent to combine map. Combine map several functional steps to produce output and update state. multiplies matrix in the state by matrix B. The result of There are two cases of these steps: this operation is matrix AB. New state item for matrix AB • When the first item arrives at grouping, it is inserted is created and sent back to the grouping. It is inserted in into the empty bucket. The grouping outputs single- bucket right after item with matrix B element tuple, and then it is sent to the combined map. • Matrix C is arrived and went through the pipeline in a Combined map generates state object and sends it back similar way as matrix B to the grouping in the form of an ordinal key-value data item. The key of the state item is the same as in the D. Handling out-of-order events item in tuple and value is the state. Combined map can generate some additional output and send it further down When we introduce the model for stateful operations, we the stream. assume that all items arrive at grouping in the right order. 25 Algorithm 2 Implementation of grouping semantics 1: function I NSERT T OMBSTONE(item, bucket) 2: cleanP osition ← lowerBound(item, bucket) 3: for all group : group ∩ cleanP osition 6= ∅ do 4: . Send tombstones for invalid groups 5: E MIT(new DataItemtomb (group)) 6: end for 7: R EMOVE(bucket, cleanP osition) 8: for all group : group ∩ cleanP osition 6= ∅ do 9: . Emit new groups that appeared after collapse 10: E MIT(new DataItem(group)) 11: end for 12: end function 13: 14: function I NSERT R EGULAR (item, bucket) 15: insertP osition ← lowerBound(item, bucket) 16: for all group : group ∩ insertP osition 6= ∅ do 17: . Send tombstones for groups that would disappear 18: . after insert 19: E MIT(new DataItemtomb (group)) 20: end for 21: I NSERT(bucket, insertP osition) 22: for all group : group ∩ insertP osition 6= ∅ do 23: . Emit new groups 24: E MIT(new DataItem(group)) 25: end for 26: end function Therefore, there is a need for barrier at the pipeline’s sink, that filters invalid items when corresponding tombstones arrive. Fig. 7. Matrix multiplication example The barrier is partially flushed for some meta-information interval when there is a guarantee that there are no any out- of-order items and tombstones further up the stream for this However, as it was shown above, it is not possible in prac- range. This guarantee can be provided by punctuations or low tice without additional buffering. We propose the following watermarks, as it is implemented in the most stream processing approach to handle events in grouping: systems. The fundamental idea behind this approach is to shift • If an item arrives in order, it is processed as usual blocking as far as possible down the stream. Notably, this is • If two items are out-of-order, and the grouping observes the only buffer in the whole system, unlike existing solutions. the second one then it is inserted into the corresponding The pseudocode for the barrier is shown in Algorithm 3. bucket at the position defined by the meta-information. The function Insert is called by the system on the new item’s After that, tuples, which contain new item are generated arrival. P unctuation is called when there is a guarantee that and sent further down the stream. At the same time, there are no tombostones up the stream with the specified for tuples, that has been produced but became invalid, time. The OOP architecture [8] can be employed to provide tombstones are sent such guarantee. Tombstones are ordinal data items but with a special flag in meta-information. This flag means that tuples with such meta- E. Advantages and limitations information are invalid, and they should not leave the system. Tombstones have the same payloads as invalid items in order The proposed architecture’s performance depends on how to go through the same path in the computational pipeline. often reorderings are observed during the runtime. In the The pseudocode of the grouping is shown in Algorithm 2. case when the order naturally preserved there is almost no The functions accept new element, depending on its type. They overhead: when the watermark arrives, all computations are also receive a bucket for element’s hash. Emit function is called already done. The probability of reordering could be managed to send new items downstream. on a business-logic level and optimized by the developer. In This technique guarantees that all correct tuples are even- experiments section it is shown that the computational nodes tually produced. However, invalid ones are also generated. count is one of such parameters. 26 Algorithm 3 Barrier grouping. The other links are implemented as simple chain 1: buf f er ← ∅ calls. 2: 3: function I NSERT(item) 4: position ← lowerBound(item, buf f er) 5: if isT ombstone(item) then 6: R EMOVE(buf f er, position) 7: else 8: I NSERT(buf f er, position) 9: end if 10: end function 11: 12: function P UNCTUATION (time) 13: for all item : item ∈ buf f er & itemts < time do 14: E MIT(item) 15: R EMOVE(item, buf f er) 16: end for 17: end function Fig. 8. Logical pipeline for inverted index Our experiments were performed on clusters of 10 nodes. Regarding the weaknesses, this method can generate ad- Each node is an AWS EC2 micro instance with 1GB RAM ditional items, which lead to extra network traffic and com- and 1 core CPU. putations. Experiments, which are shown in the section VI demonstrate that the number of extra items is low. B. Overhead and scalability VI. E XPERIMENTS As a key metric in our experiment, we take the ratio of arrived at the barrier items count to the number of the valid A. Setup items among them. This value clearly represents the overhead We performed the series of experiments to estimate the of our approach, as it was mentioned at the end of the previous performance of our system prototype. As a stream processing section. task, we apply building an inverted index. This task is chosen The relation between the number of workers, the delay because it has the following properties: between input documents and the proposed ratio is shown 1) Task requires stateful operations. It allows us to check in Figure 9. As expected, the peak of the ratio is achieved the performance of the proposed stateful pipeline when the document per second rate is high, and the number of 2) Computational flow of the task contains network shuffle the nodes is low. This behavior can be explained by the fact that can violate the ordering constraints of some op- that a few workers cannot effectively deal with such intensive erations. Therefore, inverted index task can verify the load. Nevertheless, the proportion of invalid items reduces with performance of our optimistic approach the increase of workers number. Under non-extreme load, the 3) The load distribution is skewed, because of Zipf’s law total overhead of the optimistic approach is under 10% for These properties make the task sufficient to comprehen- all considered number of workers. These results confirm that sively analyze the performance of the proposed solution. the ratio does not increase with the growth of the number of Building inverted index can be considered as the halfway nodes. task between documents generation and searching. In the real- Therefore, the most important conclusions of the experi- world, such scenario can be found in freshness-aware systems, ments are: the proposed method is scalable, the overhead could e.g., news processing engines. be optimized by system setup. The logical pipeline of this computation is shown in Figure VII. R ELATED WORK 8. First map operation accepts Wikipedia documents and outputs pairs of words and corresponding positions. The next Research works on this topic analyze different methods part of the pipeline accepts pairs of word and positions and of handling out-of-order items. Most of them are based on computes updated posting list and the actual changelog. buffering. This stateful transformation is implemented in the form of K-slack technique can be applied, if network delay is groping and map operation with a cycle, as it was shown predictable [12], [13]. The key idea of the method is the in the previous section. Regarding the physical deployment, assumption that an event can be delayed for at most K time the full logical graph is deployed on each computational unit units. Such assumption can reduce the size of the buffer. or worker. Documents are randomly shuffled before the first However, in the real-life applications, it is very uncommon map operation. Word positions are partitioned by word before to have any reliable predictions about the network delay. 27 The optimistic nature of this method is able to help to reduce the cost of waiting for punctuations or watermarks. It is implied by the fact, that at the moment when the watermark arrives all computations are already done. The experiments show that the number of the extra items 1.30 does not increase with the growth of the number of the computational units. Therefore, this approach can potentially 1.4 1.25 provide lower latency in stream processing systems. 1.20 1.3 R EFERENCES 1.15 [1] P. Carbone, A. Katsifodimos, S. Ewen, V. Markl, S. Haridi, and ratio 1.2 1.10 K. Tzoumas, “Apache flink: Stream and batch processing in a single engine,” Bulletin of the IEEE Computer Society Technical Committee 24 1.05 on Data Engineering, vol. 36, no. 4, 2015. 22 1.1 rate 20 [2] S. A. Noghabi, K. Paramasivam, Y. Pan, N. Ramesh, J. Bringhurst, 18 I. Gupta, and R. H. Campbell, “Samza: Stateful scalable stream process- (art 16 ing at linkedin,” Proc. VLDB Endow., vol. 10, no. 12, pp. 1634–1645, ic 14 10 les / 12 9 Aug. 2017. 10 6 7 8 [3] (2017, Oct.) Apache storm. [Online]. Available: http://storm.apache.org/ sec) 4 5 workers [4] S. Kulkarni, N. Bhagat, M. Fu, V. Kedigehalli, C. Kellogg, S. Mittal, J. M. Patel, K. Ramasamy, and S. Taneja, “Twitter heron: Stream processing at scale,” in Proc. of the 2015 ACM SIGMOD Intnl. Conf. on Fig. 9. The relation between the number of workers, the delay between input Management of Data, ser. SIGMOD ’15. New York, NY, USA: ACM, documents and the replay ratio 2015, pp. 239–250. [5] A. Arasu, S. Babu, and J. Widom, “The cql continuous query language: Semantic foundations and query execution,” The VLDB Journal, vol. 15, no. 2, pp. 121–142, Jun. 2006. [Online]. Available: IOP and OOP architectures, that are mentioned in the http://dx.doi.org/10.1007/s00778-004-0147-z section IV, are popular within research works and industrial [6] C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk, “Gigascope: A stream database for network applications,” in Proceedings of the applications. IOP architecture is applied in [6], [14], [5], [15], 2003 ACM SIGMOD International Conference on Management of Data, [16], [17]. OOP approach is introduced in [8] and it is widely ser. SIGMOD ’03. New York, NY, USA: ACM, 2003, pp. 647–651. used in the industrial stream processing systems, for instance, [Online]. Available: http://doi.acm.org/10.1145/872757.872838 [7] M. Hammad, W. Aref, and A. Elmagarmid, “Optimizing in-order exe- Flink [1] and Millwheel [10]. cution of continuous queries over streamed sensor data,” 2004. Optimistic techniques are less covered in literature. In [18] [8] J. Li, K. Tufte, V. Shkapenyuk, V. Papadimos, T. Johnson, and D. Maier, so-called aggressive approach is proposed. This approach “Out-of-order processing: A new architecture for high-performance stream systems,” Proc. VLDB Endow., vol. 1, no. 1, pp. 274–288, Aug. uses the idea that operation can immediately output inser- 2008. [Online]. Available: http://dx.doi.org/10.14778/1453856.1453890 tion message on the first input. After that, if that message [9] P. A. Tucker, D. Maier, T. Sheard, and L. Fegaras, “Exploiting became invalid, because of the arrival of out-of-order items, punctuation semantics in continuous data streams,” IEEE Trans. on Knowl. and Data Eng., vol. 15, no. 3, pp. 555–568, Mar. 2003. an operation can send deletion message to remove the previous [Online]. Available: http://dx.doi.org/10.1109/TKDE.2003.1198390 result and then send new insertion item. The idea of deletion [10] T. Akidau, A. Balikov, K. Bekiroğlu, S. Chernyak, J. Haberman, R. Lax, messages is very similar to our tombstone items. However, S. McVeety, D. Mills, P. Nordstrom, and S. Whittle, “Millwheel: Fault- tolerant stream processing at internet scale,” Proc. VLDB, vol. 6, no. 11, authors describe their idea in an abstract way and do not pp. 1033–1044, Aug. 2013. provide any techniques to apply their method for arbitrary [11] U. Srivastava and J. Widom, “Flexible time management in operations. data stream systems,” in Proc. PODS, ser. PODS ’04. New York, NY, USA: ACM, 2004, pp. 263–274. [Online]. Available: Yet another optimistic strategy is detailed in [19]. This http://doi.acm.org/10.1145/1055558.1055596 method is probabilistic: it guarantees the right order with some [12] S. Babu, U. Srivastava, and J. Widom, “Exploiting k-constraints to probability. Besides, it supports only the limited number of reduce memory overhead in continuous queries over data streams,” ACM Trans. Database Syst., vol. 29, no. 3, pp. 545–580, Sep. 2004. query operators. [Online]. Available: http://doi.acm.org/10.1145/1016028.1016032 [13] M. Li, M. Liu, L. Ding, E. A. Rundensteiner, and M. Mani, VIII. C ONSLUSION “Event stream processing with out-of-order data arrival,” in Proceedings of the 27th International Conference on Distributed In this paper we introduce an optimistic approach for Computing Systems Workshops, ser. ICDCSW ’07. Washington, DC, handling out-of-order events. Our technique has the following USA: IEEE Computer Society, 2007, pp. 67–. [Online]. Available: key properties: http://dx.doi.org/10.1109/ICDCSW.2007.35 [14] D. J. Abadi, D. Carney, U. Çetintemel, M. Cherniack, C. Convey, • It does not require buffering before each order-sensitive S. Lee, M. Stonebraker, N. Tatbul, and S. Zdonik, “Aurora: A new operation model and architecture for data stream management,” The VLDB Journal, vol. 12, no. 2, pp. 120–139, Aug. 2003. [Online]. Available: • The method handles properly any stateful operation http://dx.doi.org/10.1007/s00778-003-0095-z • The overhead of the proposed approach is low (under [15] L. Ding and E. A. Rundensteiner, “Evaluating window joins 10% in most of our experiments) over punctuated streams,” in Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management, • The total overhead could be managed by optimization of ser. CIKM ’04. New York, NY, USA: ACM, 2004, pp. 98–107. the computational layout [Online]. Available: http://doi.acm.org/10.1145/1031171.1031189 28 [16] M. A. Hammad, M. J. Franklin, W. G. Aref, and A. K. Elmagarmid, “Scheduling for shared window joins over data streams,” in Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29, ser. VLDB ’03. VLDB Endowment, 2003, pp. 297–308. [Online]. Available: http://dl.acm.org/citation.cfm?id=1315451.1315478 [17] M. A. Hammad, W. G. Aref, and A. K. Elmagarmid, “Optimizing in-order execution of continuous queries over streamed sensor data,” in Proceedings of the 17th International Conference on Scientific and Statistical Database Management, ser. SSDBM’2005. Berkeley, CA, US: Lawrence Berkeley Laboratory, 2005, pp. 143–146. [Online]. Available: http://dl.acm.org/citation.cfm?id=1116877.1116897 [18] M. Wei, M. Liu, M. Li, D. Golovnya, E. A. Rundensteiner, and K. Claypool, “Supporting a spectrum of out-of-order event processing technologies: From aggressive to conservative methodologies,” in Proc. of the 2009 ACM SIGMOD Intnl. Conf. on Management of Data, ser. SIGMOD ’09. New York, NY, USA: ACM, 2009, pp. 1031–1034. [19] C.-W. Li, Y. Gu, G. Yu, and B. Hong, “Aggressive complex event processing with confidence over out-of-order streams,” Journal of Computer Science and Technology, vol. 26, no. 4, pp. 685–696, Jul 2011. [Online]. Available: https://doi.org/10.1007/s11390-011-1168-x 29