Framework for supporting regular expression-based pattern matching in data streams
First Claim
Patent Images
1. A method of detecting a pattern in a data stream comprising a sequence of events, the method comprising:
- receiving, at a computerized processing system, a query that specifies a define component that specifies, for each particular symbol in a plurality of symbols in a symbol set, a separate condition that a particular event from the data stream must satisfy in order for the particular symbol to match the particular event;
receiving, at the processing system, a regular expression from the query, the regular expression specifying a pattern of symbols from the symbol set;
selecting, at a central processing unit of the processing system, a particular pattern type, based at least in part on the pattern of symbols specified in the regular expression, wherein selecting the particular pattern type comprises;
selecting the particular pattern type to be a second pattern type and not a first pattern type if any symbols in the regular expression are linked using any operator other than a concatenation operator;
based on the particular pattern type, selecting, at the processing system, a particular technique from among (a) a first technique that concurrently maintains only one binding per state in a finite state automaton constructed based on the regular expression and (b) a second technique that concurrently maintains multiple bindings per state in the finite state automaton; and
using the particular technique for detecting the pattern in the data stream;
wherein selection of the first pattern type as the particular pattern type causes the first technique to be selected as the particular technique;
wherein selection of the second pattern type as the particular pattern type causes the second technique to be selected as the particular technique;
wherein each binding maintained represents at least a partial match of the regular expression by one or more events from the data stream.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques for detecting patterns in one or more data or event streams. A pattern to be detected may be specified using a regular expression. Events received in a data stream are processed during runtime to detect occurrences of the specified pattern in the data stream. In one embodiment, a pattern type or class is determined for the specified pattern and pattern matching is performed using a technique selected based upon the type or class determined for the specified pattern.
474 Citations
12 Claims
-
1. A method of detecting a pattern in a data stream comprising a sequence of events, the method comprising:
-
receiving, at a computerized processing system, a query that specifies a define component that specifies, for each particular symbol in a plurality of symbols in a symbol set, a separate condition that a particular event from the data stream must satisfy in order for the particular symbol to match the particular event; receiving, at the processing system, a regular expression from the query, the regular expression specifying a pattern of symbols from the symbol set; selecting, at a central processing unit of the processing system, a particular pattern type, based at least in part on the pattern of symbols specified in the regular expression, wherein selecting the particular pattern type comprises; selecting the particular pattern type to be a second pattern type and not a first pattern type if any symbols in the regular expression are linked using any operator other than a concatenation operator; based on the particular pattern type, selecting, at the processing system, a particular technique from among (a) a first technique that concurrently maintains only one binding per state in a finite state automaton constructed based on the regular expression and (b) a second technique that concurrently maintains multiple bindings per state in the finite state automaton; and using the particular technique for detecting the pattern in the data stream; wherein selection of the first pattern type as the particular pattern type causes the first technique to be selected as the particular technique; wherein selection of the second pattern type as the particular pattern type causes the second technique to be selected as the particular technique; wherein each binding maintained represents at least a partial match of the regular expression by one or more events from the data stream. - View Dependent Claims (2, 3, 4)
-
-
5. A non-transitory computer-readable medium storing a plurality of instructions for controlling a data processor to detect a pattern in a data stream comprising a sequence of events, the plurality of instructions comprising:
-
instructions that cause the processor to receive a query that specifies a define component that specifies, for each particular symbol in a plurality of symbols in a symbol set, a separate condition that a particular event from the data stream must satisfy in order for the particular symbol to match the particular event; instructions that cause the processor to receive a regular expression from the query, the regular expression specifying a pattern of symbols from the symbol set; instructions that cause the processor to select a particular pattern type, based at least in part on the pattern of symbols specified in the regular expression, wherein the instructions to select the particular pattern type comprise; instructions that cause the processor to select the particular pattern type to be a second pattern type and not a first pattern type if any symbols in the regular expression are linked using any operator other than a concatenation operator; instructions that cause the processor to select, based at least in part on the particular pattern type, a particular technique from among (a) a first technique that concurrently maintains only one binding per state in a finite state automaton constructed based on the regular expression and (b) a second technique that concurrently maintains multiple bindings per state in the finite state automaton; and instructions that cause the processor to use the particular technique for detecting the pattern in the data stream; wherein the instructions that cause the processor to select the first pattern type as the particular pattern type causes the first technique to be selected as the particular technique; wherein the instructions that cause the processor to select the second pattern type as the particular pattern type causes the second technique to be selected as the particular technique; wherein each binding maintained represents at least a partial match of the regular expression by one or more events from the data stream. - View Dependent Claims (6, 7, 8)
-
-
9. A system for detecting a pattern in a data stream, the system comprising:
-
a memory storing a plurality of instructions; and a processor coupled to the memory and configured to execute the plurality instructions to; receive a query that specifies a define component that specifies, for each particular symbol in a plurality of symbols in a symbol set, a separate condition that a particular event from the data stream must satisfy in order for the particular symbol to match the particular event; receive a regular expression from the query, the regular expression specifying a pattern of symbols from the symbol set; select a particular pattern type, based at least in part on the pattern of symbols specified in the regular expression, wherein the instructions to select the particular pattern type comprise; instructions to select the particular pattern type to be a second pattern type and not a first pattern type if any symbols in the regular expression are linked using any operator other than a concatenation operator; select, based at least in part on the particular pattern type, a particular technique from among (a) a first technique that concurrently maintains only one binding per state in a finite state automaton constructed based on the regular expression and (b) a second technique that concurrently maintains multiple bindings per state in the finite state automaton; and use the particular technique for detecting the pattern in the data stream; wherein selection of the first pattern type as the particular pattern type causes the first technique to be selected as the particular technique; wherein selection of the second pattern type as the particular pattern type causes the second technique to be selected as the particular technique; wherein each binding maintained represents at least a partial match of the regular expression by one or more events from the data stream. - View Dependent Claims (10, 11, 12)
-
Specification