Systems and/or methods for forecasting future behavior of event streams in complex event processing (CEP) environments

• US 9,286,354 B2
• Filed: 08/15/2011
• Issued: 03/15/2016
• Est. Priority Date: 08/15/2011
• Status: Active Grant

• Current Assignee: Software AG
• Original Assignee: Software AG
• Inventors: Cammert, Michael, Heinz, Christoph, Krmer, Jrgen, Riemenschneider, Tobias
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Zidanic, Michael
• Application Number:
  US13/209,996
• Publication Number:
  US 20130046725A1
• Time in Patent Office: 1,674 Days
• Field of Search: 706/52
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models

Abstract

Certain example embodiments described herein relate to forecasting the future behavior of event streams in Complex Event Processing (CEP) environments. For each received event in an event stream, a reference window indicative of a predefined temporal range during which the forecast is to be computed is updated so that the reference window ends with the received event, with the reference window moving with the event stream. Within this processing loop, when a forecasting update policy indicates that the forecast is to be updated based on the received event: a forecasting window indicative of a temporal range in which events are to be forecasted is updated; and while the time period of the forecasting window is not exceeded, (a) a next forecasted event is generated via at least one processor and (b) the next forecasted event is inserted into the forecast window; and the forecast window is published.

Claims

1. A method of forecasting how an event stream will behave in the future, the method comprising:

receiving, by using at least one processor, an event stream including a plurality of events upon which a forecast is to be based; and

for each received event in the event stream;

updating, by using at least one processor, a reference window indicative of a predefined temporal range during which the forecast is to be computed so that the reference window ends with the respective received event so that the reference window moves with the event stream;

determining, by consulting a forecasting update policy, whether the forecast is to be triggered;

in response to determining the forecast is to be triggered, generating, by using at least one processor, a new forecasting window indicative of a temporal range in which events are to be forecasted;

for the new generated forecasting window and while a period of time associated with the forecasting window is not exceeded, (a) generating, via at least one processor, a plurality of forecasted events based on the updated reference window and (b) inserting the plurality of forecasted events into the new forecast window; and

publishing the new forecast window that includes the inserted plurality of forecasted events,

wherein the reference window is updated multiple times for each update of the temporal range of the new forecasting window.

2. The method of claim 1, wherein the reference window is a time-based window or a count-based window.

3. The method of claim 1, further comprising adjusting, in response to user input, the reference window to selectively emphasize either short-term or long-term stream tendencies in the event stream.

4. The method of claim 1, wherein the forecasting window is a time-based window or a count-based window.

5. The method of claim 1, wherein the forecasting update policy triggers an update upon a predefined number of events occurring or at a user-specified time interval.

6. The method of claim 1, wherein the forecasting of the plurality of forecasted events comprises, for each one of the plurality of forecasted events:

calculating a data portion for the forecasted event based on data portions of the events in the sliding reference window;

calculating a start timestamp for the forecasted event; and

calculating an end timestamp for the forecasted event.

7. The method of claim 6, wherein the start timestamp for each one of the plurality of forecasted events is calculated by adding to an immediately prior start timestamp an estimated distance to the next start timestamp.

8. The method of claim 7, wherein the estimated distance is based on distances from the reference window.

9. The method of claim 7, wherein the end timestamp for each one of the plurality of forecasted events is calculated by adding an estimated time interval length to the calculated start timestamp for the forecasted next event.

10. The method of claim 9, wherein the estimated time interval length is based on time interval lengths of events in the reference window.

11. The method of claim 6, wherein at least one of the plurality of forecasted events is used in the forecasting of another forecasted event forecasted to occur later in time.

12. The method of claim 1, wherein the forecasting of the plurality of forecasted events is practiced in accordance with a predefined forecasting strategy, the forecasting strategy including at least one strategy selected from the group consisting of:

(a) repeating values from the events in the reference window in a forward or backward manner;

(b) randomly selecting values from the events in the reference window;

(c) applying a weighted or unweighted average to values from the events in the reference window;

(d) smoothing an incrementally computed weighted average of the next event and a last estimate in accordance with a smoothing parameter controlling the emphasis of recent events;

(e) performing density-based resampling; and

(f) combining the reference window with a set of one or more predefined historic reference windows.

13. The method of claim 12, further comprising adapting parameters of the selected forecasting strategy based on an assessment of predicted event accuracy.

14. The method of claim 12, further comprising applying a conjoint estimate to data portion, event inter-arrival time, and time interval length parameters.

15. The method of claim 1, further comprising:

applying a learning algorithm to the forecast; and

adjusting the temporal range of the reference window and/or the forecasting window in response to the learning algorithm.

16. The method of claim 1, further comprising compressing events in the reference window.

17. The method of claim 16, further comprising increasing the temporal range of the reference window,

wherein the compressing and the increasing are balanced so that forecasting quality increases at a rate faster than compressing introduces error.

18. The method of claim 1, further comprising displaying business data indicative of events in the event stream along with business data indicative of forecasted events.

19. The method of claim 1, further comprising displaying system management event data along with forecasted system management event data.

20. A complex event processing (CEP) system, comprising:

at least one processor;

a CEP engine under the control of at the least one processor; and

at least one input adapter configured to receive an event stream including events and feed event data for the events from the event stream to the CEP engine;

wherein the CEP engine comprises;

at least one operator configured to directly or indirectly receive and process the event data for subsequent, direct or indirect, output to a system management application of the CEP system and/or an event consuming application or component in communication with the CEP system,

at least one forecasting operator configured to directly or indirectly receive and process the at least one said event stream by;

(a) for each received event in the event stream;

updating a reference window indicative of a predefined temporal range during which the forecast is to be computed so that the reference window ends with the received event, the reference window moving with the event stream, and

determining, by consulting a forecasting update policy, whether the forecast is to be triggered,

in response to determining the forecast is to be generated, updating a forecasting window indicative of a temporal range in which events are to be forecasted;

for the updated forecasting window and while a period of time associated with the forecasting window is not exceeded, (i) generating, via at least one processor, a plurality of forecasted events based on the updated reference window and (ii) inserting the plurality of forecasted events into the forecast window; and

publishing the forecast window that includes the inserted plurality of forecasted events, and

(b) directly or indirectly output the forecast to the system management application of the CEP system and/or an external application or component,

wherein, for each update to the temporal range of the forecasting window, the reference window is updated multiple times.

21. The CEP system of claim 20, wherein the at least one said event stream includes (1) input streams to a CEP query that is to be forecasted and (2) intermediate streams computed by other forecasting operators.

22. The CEP system of claim 20, wherein at least one of the plurality of forecasted events is generated independently of any pre-defined rule that specifies a predetermined timeframe and predetermined probability for generation of the at least one of the plurality of forecasted events.

23. A non-transitory computer readable storage medium tangibly storing instructions that are executable by at least one processor of a complex event processing (CEP) system, the stored instructions comprising instruction that are configured to cause the complex event processing (CEP) system to:

accept an event stream including a plurality of events upon which a forecast is to be based; and

for each received event in the event stream;

update a reference window indicative of a predefined temporal range during which the forecast is to be computed so that the reference window ends with the received event, the reference window moving with the event stream;

determine, by consulting a forecasting update policy that is stored on a memory device of the CEP system, whether the forecast is to be triggered;

in response to determination that the forecast is to be generated, generate a forecasting window indicative of a temporal range in which events are to be forecasted;

for the updated forecasting window and while the time period of the forecasting window is not exceeded, (a) generate a plurality of forecasted events based on the updated reference window and (b) insert the plurality of forecasted events into the forecast window; and

publish the forecast window that includes the inserted plurality of forecasted events,

wherein the forecasting update policy indicates that the forecasting window is updated only after multiple updates to the reference window have occurred.