TECHNIQUES FOR MATCHING A CERTAIN CLASS OF REGULAR EXPRESSION-BASED PATTERNS IN DATA STREAMS
First Claim
Patent Images
1. A system for detecting a pattern in a data stream comprising events, the system comprising:
- a memory storing a plurality of instructions;
a processor coupled to the memory, the processor configured to execute the plurality of instructions thereby causing the processor to;
receive predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols;
receive a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols;
maintain a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event, wherein the set of bindings comprises at most N bindings, where N is equal to a number of symbols in the regular expression plus one; and
determine if the pattern is matched due to the received event based upon the set of one or more bindings.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques for detecting patterns in data streams. A pattern to be detected may be specified using a regular expression. Events received in data streams are then processed during runtime to detect occurrences of the pattern specified by the regular expression in the data stream. If the pattern to be matched belongs to a certain predetermined class of patterns, then a pattern matching technique that is customized for that class of patterns is used during the runtime events processing.
-
Citations
20 Claims
-
1. A system for detecting a pattern in a data stream comprising events, the system comprising:
-
a memory storing a plurality of instructions; a processor coupled to the memory, the processor configured to execute the plurality of instructions thereby causing the processor to; receive predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols; receive a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols; maintain a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event, wherein the set of bindings comprises at most N bindings, where N is equal to a number of symbols in the regular expression plus one; and determine if the pattern is matched due to the received event based upon the set of one or more bindings. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer-readable storage medium storing a plurality of instructions for controlling a processor to detect a pattern in a data stream comprising events, the plurality of instructions comprising:
-
instructions that cause the processor to receive predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols; instructions that cause the processor to receive a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols; instructions that cause the processor to maintain a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event, wherein the set of bindings comprises at most N bindings, where N is equal to a number of symbols in the regular expression plus one; and instructions that cause the processor to determine if the pattern is matched due to the received event based upon the set of one or more bindings. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A method of detecting a pattern in a data stream comprising events, the method comprising:
-
receiving, at a processing system, predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols; receiving, at the processing system, a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols; maintaining, at the processing system, a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event, wherein the set of bindings comprises at most N bindings, where N is equal to a number of symbols in the regular expression plus one; determining, at the processing system, if the pattern is matched due to the received event based upon the set of one or more bindings; and outputting a set of events from the data stream that cause the pattern to be matched; wherein determining if the pattern is matched comprises; upon receiving an event in the data stream; determining one or more symbols from the set of symbols that are matched due to the received event, wherein a symbol is matched if the predicate associated with the symbol is satisfied due to the received event, determining one or more states of an automaton constructed for the pattern and associated bindings based upon the one or more symbols and based upon a set of prior states and associated bindings stored prior to receiving the received event, and determining if the pattern is matched based upon the one or more states and associated bindings.
-
Specification