Method of detecting a reference sequence of events in a sample sequence of events

• US 8,200,682 B2
• Filed: 04/22/2008
• Issued: 06/12/2012
• Est. Priority Date: 04/22/2008
• Status: Expired due to Fees

• Current Assignee: Automic Software GmbH (Broadcom, Inc.)
• Original Assignee: UC4 Software GmbH (Broadcom, Inc.)
• Inventors: Obweger, Hannes, Rauscher, Christian, Schiefer, Josef, Suntinger, Martin
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Singh, Amresh
• Application Number:
  US12/107,462
• Publication Number:
  US 20090265336A1
• Time in Patent Office: 1,512 Days
• Field of Search: 707/749, 707/758, 714/25
• US Class Current: 707/758
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A method of detecting a reference sequence of events in a sample sequence of events, wherein each event is of a certain event type and holds a set of data attributes, includes the steps of: picking candidate combinations of events from said sample sequence so that the event types within each candidate combination match the event types in the reference sequence, calculating an overall similarity score for each candidate combination from at least (i) an event occurrence score based on occurrence deviations of the events of a candidate combination with respect to the matching events of the reference sequence and (ii) an attribute match score based on similarity deviations between the data attributes of the events of a candidate combination and the data attributes of the matching events of the reference sequence, and identifying the candidate combination with the best overall similarity score as reference sequence detected.

Claims

1. A method of detecting a reference sequence of events in a sample sequence of events, wherein each event is of a certain event type and holds a set of data attributes, the method comprising:

(a) picking candidate combinations of events from said sample sequence so that the event types within each candidate combination match the event types in the reference sequence;

(b) calculating an overall similarity score for each candidate combination from at least

(i) an event occurrence score based on occurrence deviations representing a count of non-matching events between the events of a candidate combination matching events of the reference sequence, and

(ii) an attribute match score based on similarity deviations between the data attributes of the events of a candidate combination and the data attributes of the matching events of the reference sequence; and

(c) identifying the candidate combination with the best overall similarity score as reference sequence detected;

wherein the events of the candidate combinations picked from the sample sequence are put as nodes into a tree graph, each candidate combination forming a branch of the tree graph consisting of nodes connected via edges;

wherein occurrence deviations are attributed as weights to said edges and similarity deviations as weights to said nodes; and

wherein the overall similarity score of each candidate combination is calculated as a total weight accumulated along the branch formed by each candidate combination.

2. The method of claim 1, wherein the calculation of the overall similarity score is made as a weighted sum of at least the event occurrence score and the attribute match score.

3. The method of claim 1, wherein the event occurrence score is further calculated from deviations of actual occurrence times of the events of the candidate combination with respect to expected occurrence times defined in the reference sequence.

4. The method of claim 1, wherein calculating the overall similarity score for a specific candidate combination is not pursued further when the overall similarity score passes a given threshold during said calculating.

5. The method of claim 1, wherein attribute match scores are determined only for those candidate combinations for which the event occurrence scores do not pass a given threshold during the determining of the event occurrence scores.

6. The method of claim 1, wherein calculating the overall similarity score for a specific candidate combination is not pursued further when said overall similarity score passes a given threshold.

7. The method of claim 1, wherein similarity deviations are calculated only for those candidate combinations for which occurrence deviation weights do not exceed a given threshold.

8. The method of claim 1, wherein similarity deviations of said data attributes are calculated by comparing numeric or date values relative to each other or relative to given reference values.

9. The method of claim 1, wherein similarity deviations of said data attributes are calculated by comparing distances of string data attributes relative to each other or relative to given reference values.

10. The method of claim 1, wherein the reference sequence comprises time constraints, and wherein said overall similarity score is calculated additionally from

(iii) a time constraint violation score based on time constraint violations of the events of a candidate combination with respect to said time constraints.

11. The method of claim 9, wherein at least one time constraint is a time window for events to occur in order not to violate said time constraint.

12. The method of claim 1, wherein the reference sequence comprises arrangement constraints, and wherein said overall similarity score is calculated additionally from

(iv) an arrangement constraint violation score based on arrangement constraint violations due to the order of events in a candidate combination with respect to said arrangement constraint.

13. The method of claim 12, wherein at least one arrangement constraint can weaken the weight of the event occurrence score in the overall similarity score.

14. The method of claim 1, wherein event count constraints are set in the reference sequence, and wherein said overall similarity score is calculated additionally from

(v) an event count constraint violation score based on event count violations by excessive occurrences of events of a certain event type with respect to said event count constraint.

15. The method of claim 1, wherein the reference sequence comprises a wildcard event which can be matched by any event of a candidate combination.

16. The method of claim 1, wherein the events of the sample sequence are correlated.

17. The method of claim 1, wherein at least some of the events are nested.