×

Techniques for performing regular expression-based pattern matching in data streams

  • US 8,589,436 B2
  • Filed: 08/26/2009
  • Issued: 11/19/2013
  • Est. Priority Date: 08/29/2008
  • Status: Active Grant
First Claim
Patent Images

1. A method of detecting a pattern in a data stream comprising events, the method comprising:

  • receiving, at a processing system, including a processor, predicate information, the predicate information specifying a predicate associated with each symbol in a set of symbols, the predicate information including a first predicate associated with a first symbol in the set of symbols, and including a second predicate associated with a second symbol in the set of 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;

    constructing an automaton for the pattern;

    upon receiving an event in the data stream;

    determining, based upon the received event, states of the automaton and associated bindings, anddetermining if the pattern is matched due to the received event based upon the states and associated bindings;

    in response to determining that the pattern is matched by a particular sequence of events in the data stream, continuing to determine whether subsequent events following the particular sequence of events in the data stream produce a match that is longer than a match produced by the particular sequence of events; and

    outputting the match produced by the particular sequence of events only after determining that no match longer than the match produced by the particular sequence of events is possible based on the states and associated bindings.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×