Back to results
US 9,002,861 B2Granted
Matching device and computer-readable storage medium
AssigneeFujitsu Limited
InventorsTatsuya Asai, Hiroaki Morikawa, Shinichiro Tago, Hiroya Inakoshi, Nobuhiro Yugami, Seishi Okamoto
Life of this patent
Estimating the term…
Abstract
A matching device builds a parse tree from an event pattern. The matching device builds an automaton by, while traversing the parse tree, joining child nodes of an AND node in parallel to the AND node and joining child nodes of an OR node in parallel to the OR node. The matching device performs matching of determining whether an event stream includes the event pattern by comparing the event stream with the automaton.
Claims10
A matching device comprising:
- a processor;
- and
- a memory, wherein the processor executes:
- building a parse tree based on an event pattern representing an occurrence order of a first pattern, a second pattern, and a third pattern,
- the first pattern being a single event,
- the second pattern being a pattern where every event of a plurality of events occurs,
- the third pattern being a pattern where any one event of a plurality of events occurs,
- the parse tree associating an event node, an AND node representing a relationship between the events in the second pattern, and an OR node representing a relationship between the events of the third pattern, together in a tree structure;
- building an automaton by performing a process of joining first child nodes of the AND node in parallel to the AND node, a process of setting a first transition from the first child node to the AND node, a process of joining second child nodes of the OR node in parallel to the OR node and a process of setting a second transition from the second child node to the OR node, while traversing the parse tree, wherein the first transition is invoked when the event of the first child node has occurred and the second transition is invoked when the event of the second child node has occurred;
- and
- performing matching of determining whether an event stream that includes a plurality of event occurrence orders includes the event pattern by
- comparing the event stream with the automaton in succession,
- causing a transition to the AND node of the automaton to start after two of the first transitions to the AND node have been invoked, and
- causing a transition to the OR node of the automaton to start after one of the second transitions to the OR node has been invoked.
11 more elements
A non-transitory computer readable storage medium having stored therein a matching program, the matching program causing a computer to execute a process comprising:
- building a parse tree based on an event pattern representing an occurrence order of a first pattern, a second pattern, and a third pattern,
- the first pattern being a single event,
- the second pattern being a pattern where every event of a plurality of events occurs,
- the third pattern being a pattern where any one event of a plurality of events occurs,
- the parse tree associating an event node, an AND node representing a relationship between the events in the second pattern, and an OR node representing a relationship between the events of the third pattern together in a tree structure;
- building an automaton by performing, while traversing the parse tree stored in the storage device, a process of joining first child nodes of the AND node in parallel to the AND node, a process of setting a first transition from the first child node to the AND node, a process of joining second child nodes of the OR node in parallel to the OR node and a process of setting a second transition from the second child node to the OR node;
- storing the automaton in a storage device;
- and
- performing matching of determining whether an event stream that includes a plurality of event occurrence orders includes the event pattern by
- comparing the event stream with the automaton in succession,
- causing a transition to the AND node of the automaton to start after two of the first transitions to the AND node have been invoked, and
- causing a transition to the OR node of the automaton to start after one of the second transitions to the OR node has been invoked.
9 more elements
Dependencies are inferred from the claim text.