DYNAMIC PATTERN MATCHING OVER ORDERED AND DISORDERED DATA STREAMS

• US 20110282812A1
• Filed: 05/17/2010
• Published: 11/17/2011
• Est. Priority Date: 05/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ali, Mohamed H., Goldstein, Jonathan D., Maier, David, Chandramouli, Badrish, Schindlauer, Roman
• Granted Patent: US 8,762,297 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Architecture introduces a new pattern operator referred to as called an augmented transition network (ATN), which is a streaming adaptation of non-reentrant, fixed-state ATNs for dynamic patterns. Additional user-defined information is associated with automaton states and is accessible to transitions during execution. ATNs are created that directly model complex pattern continuous queries with arbitrary cycles in a transition graph. The architecture can express the desire to ignore some events during pattern detection, and can also detect the absence of data as part of a pattern. The architecture facilitates efficient support for negation, ignorable events, and state cleanup based on predicate punctuations.

Claims

1. A computer-implemented data stream management system having computer readable media that store executable instructions executed by a processor, comprising:

an input component that receives streaming data having a pattern of events to be matched; and

a pattern-matching operator that operates over the streaming data to find the pattern based on a pattern definition also received as a streaming input, the pattern definition characterizes the pattern as an automaton having states represented as nodes and transitions between the states represented as arcs.

2. The system of claim 1, wherein the automaton states have associated data of a form specified by a user that facilitates expressive pattern matching.

3. The system of claim 2, wherein an arc in the automata has associated user-defined information that includes a fence function that indicates if transition along an arc can occur based on data associated with states, and a transfer function that computes new values for the data associated with states.

4. The system of claim 1, wherein the pattern-matching operator processes ordered and disordered patterns of the streaming data.

5. The system of claim 1, wherein the pattern-matching operator handles negative patterns without first generating false-positive patterns.

6. The system of claim 1, wherein the pattern-matching operator facilitates introduction of a user-defined operator.

7. The system of claim 1, further comprising a pattern matching component that employs an event algorithm that, optionally, processes ignorable events of the streaming data.

8. The system of claim 1, further comprising a pattern matching component that employs a cleanup algorithm which performs punctuation-based cleanup to delete partial match events.

9. A computer-implemented data stream management system having computer readable media that store executable instructions executed by a processor, comprising:

an input component that receives streaming data having a pattern of events to be matched; and

a pattern-matching operator that operates over the streaming data to find the pattern based on a pattern definition received as a streaming input, the pattern definition characterizes the pattern as an automaton having states represented as nodes and transitions between the states represented as arcs, the automaton states having associated data of a form specified by a user that facilitates expressive pattern matching.

10. The system of claim 9, wherein an arc in the automata has associated user-defined information that includes a fence function that indicates if transition along an arc can occur based on data associated with states, and a transfer function that computes new values for the data associated with states.

11. The system of claim 9, wherein the pattern-matching operator processes ordered and disordered patterns of the streaming data and handles negative patterns without first generating false-positive patterns.

12. The system of claim 9, wherein the pattern-matching operator facilitates introduction of a user-defined operator.

13. The system of claim 9, further comprising a pattern matching component that employs an event algorithm that, optionally, processes ignorable events of the streaming data and a cleanup algorithm that performs punctuation-based cleanup to delete partial match events.

14. The system of claim 13, wherein the pattern matching component controls speculation based on pre-computation of expected out-of-order events in the streaming data, and event indexing by sequence numbers or timestamps, and optionally employs predicated punctuation and a graph structure to determine registers and events for deletion.

15. A computer-implemented data stream management method executed by a processor, comprising:

receiving streaming data having patterns of events to be detected;

applying a pattern-matching operator to the streaming data to match patterns in the streaming data;

matching a pattern based on a pattern definition of the pattern-matching operator that characterizes the pattern as an automaton having states represented as nodes and transitions between the states represented as arcs; and

outputting streaming data of matched pattern instances.

16. The method of claim 15, further comprising processing ignorable events in the streaming data.

17. The method of claim 15, further comprising executing a cleanup algorithm to perform punctuation-based cleanup to delete partial match events.

18. The method of claim 15, further comprising processing negative patterns without first generating false-positive patterns.

19. The method of claim 15, further comprising processing disordered data streams using new events and by modifying or deleting existing older events.

20. The method of claim 15, further comprising associating user functions that manipulate register values of active automaton states at runtime.