Detection of recurring non-occurrences of events using pattern matching

• US 8,676,841 B2
• Filed: 08/26/2009
• Issued: 03/18/2014
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Srinivasan, Anand, Komuravelli, Rakesh, Mishra, Shailendra
• Primary Examiner(s): Corrielus, Jean M
• Assistant Examiner(s): ASPINWALL, EVAN S
• Application Number:
  US12/548,290
• Publication Number:
  US 20100057727A1
• Time in Patent Office: 1,665 Days
• Field of Search: 707/713, 707/758, 707/759, 707/760, 707/761, 707/762, 707/763, 707/765, 707/769, 707/771, 707/772, 707/779, 707/E17.014, 707/E17.017, 707/E17.061, 707/E17.062, 707/E17.063, 707/E17.069, 707/999.003, 707/780, 712/220
• US Class Current: 707/780
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/20 Analysing

Abstract

Techniques for detecting recurring non-occurrences of an event. In one embodiment, techniques are provided for detecting the non-occurrence of an event within each of a series of time periods following the occurrence of another event. Language extensions are provided that enable queries to be formulated for detecting recurring non-occurrence of an event following occurrence of a triggering event.

Claims

1. A computer-readable non-transitory storage medium storing a plurality of instructions for controlling a processor to process a data stream of events being continuously received by the processor over time, the plurality of instructions comprising:

instructions that cause the processor to receive a query for detecting recurrence of a non-occurrence of a first event within each of a series of multiple time periods, wherein the first time period in the series of multiple time periods starts upon occurrence of a second event, the query specifying (a) a pattern of symbols that are matched by occurrences of events in the data stream being continuously received by the processor over time, and (b) a time duration specifying a length of time for each of the time periods in the series of multiple time periods;

instructions that cause the processor to generate a modified pattern based on the pattern of symbols;

instructions that cause the processor to generate an automaton for the query based upon the modified pattern; and

instructions that cause the processor to perform processing for detecting recurrence of non-occurrence of the first event within each time period of the series of multiple time periods following occurrence of the second event using the automaton by detecting a separate non-occurrence of the first event for each particular time period of the multiple time periods in which the first event does not occur, regardless of whether the second event re-occurs in that particular time period.

2. The computer-readable non-transitory storage medium of claim 1 wherein the plurality of instructions comprises instructions that cause the processor to stop detecting non-occurrence of the first event in the series of time periods when a stoppage condition is met.

3. The computer-readable non-transitory storage medium of claim 1 wherein the plurality of instructions further comprises:

instructions that cause the processor to determine whether the query is for detecting non-occurrence of the first event; and

instructions that cause the processor to generate the modified pattern upon determining that the query is for detecting non-occurrence of the first event by adding, to the pattern, a first symbol that is matched by passage of time rather than by occurrence of an event in the data stream being continuously received by the processor over time.

4. The computer-readable non-transitory storage medium of claim 1 wherein the instructions that cause the processor to perform processing for detecting non-occurrence of the first event comprise:

instructions that cause the processor to, for a time period in the series of time periods,

associate a target time with a binding, the binding representing a degree to which one or more events received in the data stream match the pattern, wherein the target time associated with the binding is determined based upon a time associated with an event corresponding to a first element in the binding and the time duration,

receive an input, and

compare a time associated with the input with the target time.

5. The computer-readable non-transitory storage medium of claim 2 where the stoppage condition is occurrence of the first event.

6. The computer-readable non-transitory storage medium of claim 4 wherein the input is a heartbeat or another event received in the data stream.

7. The computer-readable non-transitory storage medium of claim 4 wherein the instructions that cause the processor to perform processing for detecting non-occurrence of the first event comprise:

instructions that cause the processor to, upon determining that the time associated with the input equals or exceeds the target time, cause the automaton to move to a final state.

8. The computer-readable non-transitory storage medium of claim 7 wherein the instructions that cause the processor to perform processing for detecting non-occurrence of the first event comprise:

instructions that cause the processor to, upon the automaton moving to the final state, output an indication of non-occurrence of the first event within a time period in the series of time periods.

9. A system for processing a data stream of events being continuously received by the system over time, the system comprising:

a memory storing a plurality of instructions; and

a processor coupled to the memory, the processor configured to execute the plurality of instructions to;

receive a query for detecting recurrence of a non-occurrence of a first event within each of a series of multiple time periods, wherein the first time period in the series of multiple time periods starts upon occurrence of a second event, the query specifying (a) a pattern of symbols that are matched by occurrences of events in the data stream being continuously received by the system over time, and (b) a time duration specifying a length of time for each of the time periods in the series of multiple time periods;

generate a modified pattern based on the pattern of symbols;

generate an automaton for the query based upon the modified pattern; and

perform processing for detecting recurrence of non-occurrence of the first event within each time period of the series of multiple time periods following occurrence, at a beginning of the series, of the second event using the automaton.

10. The system of claim 9 wherein the processor is configured to:

determine whether the query is for detecting non-occurrence of the first event; and

generate the modified pattern upon determining that the query is for detecting non-occurrence of the first event by adding, to the pattern, a first symbol that is matched by passage of time rather than by occurrence of an event in the data stream being continuously received by the processor over time.

11. The system of claim 9 wherein the processor is configured to:

for a time period in the series of time periods;

associate a target time with a binding, the binding representing a degree to which one or more events received in the data stream match the pattern, wherein the target time associated with the binding is determined based upon a time associated with an event corresponding to a first element in the binding and the time duration,

receive an input, and

compare a time associated with the input with the target time.

12. The system of claim 11 wherein the input is a heartbeat or another event received in the data stream.

13. The system of claim 11 wherein the processor is configured to, upon determining that the time associated with the input equals or exceeds the target time, cause the automaton to move to a final state.

14. The system of claim 13 wherein the processor is configured to, upon the automaton moving to the final state, output an indication of non-occurrence of the first event within a time period in the series of time periods.

15. A computer-implemented method for processing a data stream of events being continuously received by a processing system over time, the method comprising:

receiving, by the processing system, a query for detecting recurrence of non-occurrence of a first event within each time period of a series of multiple time periods, wherein the first time period in the series of time periods starts upon occurrence of a second event, the query specifying (a) a pattern of symbols that are matched by occurrences of events in the data stream being continuously received by the processor over time, and (b) a time duration specifying a length of time for each of the time periods in the series of time periods;

generating, by the processing system, a modified pattern by adding, to the pattern, a first symbol that is matched by passage of time rather than by occurrence of an event in the data stream being continuously received by the processor over time;

generating, by at least one central processing unit of the processing system, an automaton for the query based upon the modified pattern; and

performing processing, by the processing system, for separately detecting non-occurrence of the first event within each particular time period of the series of multiple time periods following occurrence of the second event using the automaton.

16. The method of claim 15 wherein performing processing for detecting non-occurrence of the first event comprises:

for a time period in the series of time periods;

associating, by the processing system, a target time with a binding, the binding representing a degree to which one or more events received in the data stream match the pattern, wherein the target time associated with the binding is determined based upon a time associated with an event corresponding to a first element in the binding and the time duration,

receiving, by the processing system, an input, and

comparing, by the processing system, a time associated with the input with the target time.

17. The method of claim 16 wherein the input is a heartbeat or another event received in the data stream.

18. The method of claim 16 wherein performing processing for detecting non-occurrence of the first event further comprises, upon determining that the time associated with the input equals or exceeds the target time, causing the automaton to move to a final state.

19. The method of claim 18 wherein performing processing for detecting non-occurrence of the first event further comprises, upon the automaton moving to the final state, outputting an indication of non-occurrence of the first event within a time period in the series of time periods.