Dynamic pattern matching code generation

Patent metadata

Field	Value
Publication number	US-11093218-B2
Application number	US-201715650455-A
Country	US
Kind code	B2
Filing date	Jul 14, 2017
Priority date	Jul 14, 2017
Publication date	Aug 17, 2021
Grant date	Aug 17, 2021

Abstract

An intermediate representation of a workflow of one or more modules may be generated to decouple language implementations of the one or more modules. In response to receiving a workflow of one or more modules, the workflow may be analyzed to determine an optimal implementation language for each of the one or more modules to thereby reduce effects of data marshalling. An intermediate representation of the workflow that is configured to decouple any implementation languages associated with the one or more modules may be generated. To allow for decoupling, the intermediate representation may be written in a declarative language. The generated intermediate representation may then be compiled to generate an executable program that corresponds to the workflow and is implemented in the determined optimal language for each of the one or more modules.

First claim

What is claimed:

1. A computer system comprising:
one or more processors; and
one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to generate code that is specific to a particular augmented finite automaton for efficient identification of patterns within a stream of data, the identification of patterns being based on processing one or more events in the stream of data, the computer-executable instructions including instructions that are executable to configure the computer system to perform at least the following:
access a specification corresponding to an augmented finite automaton that is configured to identify one or more patterns within a stream of data, the augmented finite automaton comprising a directed graph with nodes representing states of pattern detection, with edges between the nodes comprising arcs that define transitions between the different states, each arc including a fence function and a transfer function, the fence function defining when each corresponding arc is triggered and the transfer function including a counter element for tracking a count within a register associated with the corresponding arc, wherein the fence function and the transfer function are operable to define conditions for the augmented finite automaton to transition from one state to another state while identifying events and/or patterns within the stream of data;
analyze the specification corresponding to the augmented finite automaton;
based on the analysis of the specification corresponding to the augmented finite automaton, identify one or more characteristics associated with the specification corresponding to the augmented finite automaton, the one or more characteristics including at least the transfer function and the fence function for a corresponding arc;
based on the identified one or more characteristics, dynamically generate code specific to the augmented finite automaton that is configured to identify the one or more patterns within the stream of data by at least transitioning between different states in response to a triggering of the corresponding arc caused by the fence function and the transfer function being satisfied; and
configure the code to identify events in the stream of data and to process the events to identify patterns in the stream of data by at least configuring the code to cause transitioning between the different states of pattern detection according to the augmented finite automaton specification in response to event data in the stream of data satisfying the fence function and the transfer function for triggering the corresponding arc associated with the transitioning.

2. The computer system in accordance with claim 1 , wherein the accessed specification corresponding to the augmented finite automaton comprises an augmented finite automaton that has been generated using a software programming language.

3. The computer system in accordance with claim 2 , wherein the software programming language comprises one or more of C#, C++, and Java.

4. The computer system in accordance with claim 1 , wherein the one or more characteristics associated with the specification corresponding to the augmented finite automaton further comprises at least a grouping factor and at least a determinism factor.

5. The computer system in accordance with claim 1 , wherein the computer-executable instructions further include instructions that are executable to cause the computer system to, in response to receiving the stream of data, utilize the dynamically generated code to identify the one or more patterns within the stream of data.

6. The computer system in accordance with claim 1 , wherein the register is configured to aid in identifying complex patterns within the stream of data.

7. The computer system in accordance with claim 1 , wherein based on the one or more characteristics associated with the specification corresponding to the augmented finite automaton, the dynamically generated code is further configured to identify overlapping instances of pattern matches.

8. A method, implemented at a computer system that includes one or more processors, for generating code that is specific to a particular augmented finite automaton for efficient identification of patterns within a stream of data, the identification of patterns being based on processing one or more events in the stream of data, comprising:
accessing a specification corresponding to an augmented finite automaton that is configured to identify one or more patterns within a stream of data, the augmented finite automaton comprising a directed graph with nodes representing states of pattern detection, with edges between the nodes comprising arcs that define transitions between the different states, each arc including a fence function and a transfer function, the fence function defining when each corresponding arc is triggered and the transfer function including a counter element for tracking a count within a register associated with the corresponding arc, wherein the fence function and the transfer function are operable to define conditions for the augmented finite automaton to transition from one state to another state while identifying events and/or patterns within the stream of data;
analyzing the specification corresponding to the augmented finite automaton;
based on the analysis of the specification corresponding to the augmented finite automaton, identifying one or more characteristics associated with the specification corresponding to the augmented finite automaton, the one or more characteristics including at least the transfer function and the fence function for a corresponding arc;
based on the identified one or more characteristics, dynamically generating code specific to the augmented finite automaton that is configured to identify the one or more patterns within the stream of data by at least transitioning between different states in response to a triggering of the corresponding arc caused by the fence function and the transfer function being satisfied; and
configuring the code to identify events in the stream of data and to process the events to identify patterns in the stream of data by at least configuring the code to cause transitioning between the different states of pattern detection according to the augmented finite automaton specification in response to event data in the stream of data satisfying the fence function and the transfer function for triggering the corresponding arc associated with the transitioning.

9. The method in accordance with claim 8 , wherein the accessed specification corresponding to the augmented finite automaton comprises an augmented finite automaton that has been generated using a software programming language.

10. The method in accordance with claim 9 , wherein the software programming language comprises one or more of C#, C++, and Java.

11. The method in accordance with claim 8 , wherein the one or more characteristics associated with the specification corresponding to the augmented finite automaton further comprises at least a grouping factor and at least a determinism factor.

12. The method in accordance with claim 8 , further comprising, in response to receiving the stream of data, utilizing the dynamically generated code to identify the one or more patterns within the stream of data.

13. The method in accordance with claim 8 , wherein the register is configured to aid in identifying complex patterns within the stream of data.

14. The method in accordance with claim 8 , wherein the specification corresponding to th

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Chandramouli Badrish
• Goldstein Jonathan D
• Barnett Michael
• Terwilliger James Felger

Classifications

• G06F16/90344 Primary

  by using string matching techniques · CPC title

• G06N99/00

  Subject matter not provided for in other groups of this subclass · CPC title

• G06F9/45516

  Runtime code conversion or optimisation · CPC title

• G06F8/315 Primary

  Object-oriented languages · CPC title