DETECTION OF RECURRING NON-OCCURRENCES OF EVENTS USING PATTERN MATCHING

• US 20100057727A1
• Filed: 08/26/2009
• Published: 03/04/2010
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mishra, Shailendra, Komuravelli, Rakesh, Srinivasan, Anand
• Granted Patent: US 8,676,841 B2
• Time in Patent Office: Days
• US Class Current: N/A
• 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 storage medium storing a plurality of instructions for controlling a processor to process a data stream of events, the plurality of instructions comprising:

instructions that cause the processor to receive a query for detecting non-occurrence of a first event within each of a series of time periods, wherein the first time period in the series of time periods starts upon occurrence of a second event, the query specifying a pattern and a time duration specifying a length of time for each of the time periods in the series of time periods;

instructions that cause the processor to generate a modified pattern by adding a first symbol to the pattern;

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 non-occurrence of the first event within each of the series of time periods following occurrence of the second event using the automaton.

2. The computer-readable 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 storage medium of claim 2 where the stoppage condition is occurrence of the first event.

4. The computer-readable 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 only upon determining that the query is for detecting non-occurrence of the first event.

5. The computer-readable 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.

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

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

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 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, 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 non-occurrence of a first event within each of a series of time periods, wherein the first time period in the series of time periods starts upon occurrence of a second event, the query specifying a pattern and a time duration specifying a length of time for each of the time periods in the series of time periods;

generate a modified pattern by adding a first symbol to the pattern;

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

perform processing for detecting non-occurrence of the first event within each of the series of time periods following occurrence 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 only upon determining that the query is for detecting non-occurrence of the first event.

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 method for processing a data stream of events, the method comprising:

receiving, by a processing system, a query for detecting non-occurrence of a first event within each of a series of time periods, wherein the first time period in the series of time periods starts upon occurrence of a second event, the query specifying a pattern and 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 a first symbol to the pattern;

generating, by the processing system, an automaton for the query based upon the modified pattern; and

performing processing, by the processing system, for detecting non-occurrence of the first event within each of the series of 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.