System and method for analyzing a pattern in a time-stamped event sequence

• US 20050235356A1
• Filed: 04/09/2004
• Published: 10/20/2005
• Est. Priority Date: 04/09/2004
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Wang, Changzhou
• Granted Patent: US 7,447,666 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

Preferred embodiments and implementations include a system and method for determining distinct occurrences of a pattern in a sequence of time-stamped event instances by determining a maximum cardinality of disjoint occurrences of the pattern in the one or more sequences. The invention also includes estimating an expected quantity of distinct occurrences of a pattern in a sequence of time-stamped events assigned to event categories. The invention further includes identifying a surprise pattern within a sequence of time-stamped events.

Claims

1. A method of determining distinct occurrences of a pattern in one or more sequences of time-stamped event instances, the method comprising:

determining a maximum cardinality of disjoint occurrences of the pattern in the one or more sequences.

2. The method of claim 1 wherein determining the maximum cardinality comprises counting a quantity of disjoint occurrence sets in the one or more sequences.

3. The method of claim 1 wherein determining the maximum cardinality comprises:

determining occurrences of the pattern in the one or more sequences; and

identifying a disjoint occurrence from the occurrences.

4. The method of claim 3, further comprising determining the maximum cardinality as a function of counting a quantity of identified disjoint occurrences.

5. The method of claim 3 wherein identifying occurrences includes matching event instances to a group within the pattern, and matching matched groups to the pattern.

6. The method of claim 5 wherein matching event instances to a group within a pattern includes determining that the matched event instances are within a group window size constraint of the group.

7. The method of claim 5 wherein matching matched groups to the pattern includes applying an upper time gap constraint of the pattern to the two or more matched groups.

8. The method of claim 5 wherein matching matched groups to the pattern includes applying a lower time gap constraint of the pattern to the two or more matched groups.

9. The method of claim 5, further comprising removing an event instance that is included in the identified disjoint occurrence from the sequence of time-stamped event instances.

10. The method of claim 9, further comprising repeating the method to identify further disjoint occurrences wherein the removed event instances are not included in the identification of more than one disjoint occurrence of the pattern.

11. The method of claim 5, further comprising flagging an event instance that is included in the identified disjoint occurrence from the sequence of time-stamped event instances.

12. The method of claim 11, further comprising repeating the method to identify further disjoint occurrences wherein the flagged event instances are not included in the identification of more than one disjoint occurrence of the pattern.

13. The method of claim 3 wherein a first occurrence is disjoint from a second occurrence when an intersection of event instances between the first occurrence and the second distinct occurrence is null.

14. The method of claim 3 wherein a first occurrence is disjoint to a second occurrence when an event instance occurs in only one of the first occurrence and the second occurrence.

15. The method of claim 3 wherein the event instances within the sequence are categorized into a predetermined set of categories.

16. The method of claim 3 wherein identifying occurrences includes matching categories of event instances to a group within the pattern, and matching matched categories to the pattern.

17. The method of claim 1 wherein determining includes:

matching a group of event categories to the sequence to identify an occurrence of the group within the sequence;

identifying a fully matched group wherein the event instances comprising the matched group are within a temporal window width defined by the group;

identifying an occurrence of the pattern by determining that a first matched group is within a temporal window of a second matched group, said temporal window defining the temporal relationship between the first group and the second group;

identifying event instances composing each identified pattern occurrence;

identifying disjoint occurrences from the identified pattern occurrences, wherein a particular event instance is an event instance in only one disjoint occurrence of the pattern; and

summing a count of all identified disjoint occurrences, said sum being the maximum cardinality of the pattern in the sequence.

18. The method of claim 1 wherein a parameter defining the pattern is at least one from the group consisting of an event instance, a category, a group, a minimum time gap, a maximum time gap, and a window size.

19. The method of claim 1 wherein the sequence comprises a temporal overlap of at least one occurrence of the pattern with another occurrence of the pattern.

20. The method of claim 1 wherein the time-stamped event instances are one or more events from the group consisting of an operation of a work device, a purchase, a bid, an action, a message, an event, and a score.

21. The method of claim 1 wherein a work device is an airplane and the time-stamped event instances are events associated with operations of the airplane.

22. The method of claim 21 wherein the disjoint occurrence is indicative of a required maintenance procedure associated with the work device.

23. The method of claim 1 wherein the two or more sequences are indicative of two or more airplanes comprising a fleet of airplanes and the time-stamped event instances are events associated with operations of the two or more airplanes within the fleet of airplanes.

24. The method of claim 1 wherein an event instance includes one or more from the group consisting of a purchase, a sale, a transaction, a score, an alarm, a failure, an action, a bid, an omission, a request, an order, a message, an attempt, an interruption, a cancellation, and a change of a parameter.

25. A method of estimating an expected quantity of distinct occurrences of a pattern in a sequence of time-stamped events, said time stamped events being assigned to event categories, said pattern having a first event category and a second event category, the second event category being within a time gap of the first event category, said time gap having a minimum time gap and a maximum time gap, said sequence having a maximum time length, the method comprising:

counting instances of the first event in the sequence;

counting instances of the second event in the sequence; and

determining the expected quantity of distinct occurrences of the pattern as a function of the quantity of first event instances, the quantity of second event instances, the maximum time length of the sequence, the minimum time gap, and the maximum time gap.

26. The method of claim 25 wherein determining the expected quantity of distinct occurrences of the pattern includes calculating a lower bound and an upper bound of a mean of the expected quantity of distinct occurrences of the pattern in the sequence.

27. The method of claim 26 wherein calculating the lower bound and the upper bound of the mean of the expected quantity of distinct occurrences is a function of the minimum time gap and the maximum time gap over the maximum time length of the sequence.

28. The method of claim 26 wherein calculating the lower bound and the upper bound of the mean includes:

determining an initial lower bound and an initial upper bound of the mean as a function of one or more from the group consisting of an estimation coefficient, an alternating adjustment factor, a base estimation of the mean of the expected quantity, an incremental estimation parameter, a estimation adjustment parameter, an estimation precision objective, the maximum time length of the sequence, the minimum time gap, and the maximum time gap.

29. The method of claim 26 wherein determining the expected quantity of distinct occurrences of the pattern comprises:

calculating a base estimation of a mean of an expected maximum cardinality;

determining an initial lower bound of the mean of the expected maximum cardinality as a function of the base estimation and an incremental estimation parameter;

determining an initial upper bound of the mean of the expected maximum cardinality as a function of the base estimation, an incremental estimation parameter, and an estimation adjustment parameter.

30. The method of claim 29, further comprising:

recalculating at least one of the initial lower bound and the initial upper bound of the mean of the expected maximum cardinality to determine at least one of a refined lower bound and a refined upper bound when the difference between the initial upper bound and the initial lower bound is greater than a precision objective.

31. The method of claim 30 wherein the precision objective is the product of an estimation precision objective and at least one of the initial lower bound and the refined lower bound.

32. The method of claim 30 wherein recalculating continues until the difference between a calculated upper bound and a calculated lower bound is less than or equal to the precision objective.

33. The method of claim 25 wherein the pattern comprises a complex pattern, said complex pattern having two or more sub-patterns wherein at least one sub-pattern includes two or more events, further comprising:

segmenting the complex pattern into a first sub-pattern and a second sub-pattern;

counting a quantity of the first sub-pattern in the sequence; and

counting a quantity of the second sub-pattern in the sequence,

wherein determining the expected quantity of distinct occurrences of the complex pattern is a function of the quantity of the first sub-pattern and the quantity of the second sub-pattern.

40. A method of identifying a surprise pattern within a sequence of time-stamped event instances, the method comprising:

calculating an expected quantity of distinct occurrences of a pattern in the sequence;

determining a maximum cardinality of the pattern in the sequence; and

identifying the surprise pattern as a function of the estimated quantity of distinct occurrences and the maximum cardinality.

41. The method of claim 40 wherein determining a surprise pattern includes determining an occurrence ratio as the ratio of the maximum cardinality over the expected quantity of distinct occurrences.

42. The method of claim 41 wherein an occurrence ratio greater than a predetermined surprise pattern threshold is indicative of a surprise pattern.

43. The method of claim 42 wherein the predetermined surprise pattern threshold is 20 percent.

44. The method of claim 40 wherein the maximum cardinality is a sum of a number of disjoint occurrences of the pattern in the sequence.

45. The method of claim 44 wherein a first disjoint occurrence is disjoint from a second disjoint occurrence such that an event instance is present in only one of the first disjoint occurrence and the second disjoint occurrence.

46. The method of claim 40 wherein determining the maximum cardinality includes:

identifying occurrences of the pattern in the sequence; and

identifying a disjoint occurrence from the occurrences.

47. The method of claim 40 wherein calculating the expected quantity of discrete occurrences includes:

counting first event instances in the sequence;

counting second event instances in the sequence; and

determining the expected quantity of distinct occurrences of the pattern as a function of the quantity of first event instances, the quantity of second event instances, a maximum time length of the sequence, and a minimum time gap and a maximum time gap between the second event instance and the first event instance.

48. A system for determining distinct occurrences of a pattern in a sequence of time-stamped event instances, the system comprising:

means for storing the sequence;

means for defining the pattern; and

means for determining a maximum cardinality of disjoint occurrences of the pattern in the sequence.

49. The system of claim 48 wherein the time-stamped event instances include events associated with an operation of an aircraft.

50. Computer readable medium including computer executable instructions for determining distinct occurrences of a pattern in a sequence of time-stamped event instances, the computer instructions comprising means for determining a maximum cardinality of disjoint occurrences of the pattern in the sequence.

51. A system for estimating an expected quantity of distinct occurrences of a pattern in a sequence of time-stamped events, time stamped events being assigned to event categories, said pattern having a first event category and a second event category, the second event category being within a time gap of the first event category, said time gap having a minimum time gap and a maximum time gap, said sequence having a maximum time length, the system comprising:

means for counting instances of the first event in the sequence;

means for counting instances of the second event in the sequence; and

means for determining the expected quantity of distinct occurrences of the pattern as a function of the quantity of first event instances, the quantity of second event instances, the maximum time length of the sequence, the minimum time gap, and the maximum time gap.

52. Computer readable medium including computer executable instructions for estimating an expected quantity of distinct occurrences of a pattern in a sequence of time-stamped events, time stamped events being assigned to event categories, said pattern having a first event category and a second event category, the second event category being within a time gap of the first event category, said time gap having a minimum time gap and a maximum time gap, said sequence having a maximum time length, the computer executable instructions comprising:

means for counting instances of the first event in the sequence;

means for counting instances of the second event in the sequence; and

means for determining the expected quantity of distinct occurrences of the pattern as a function of the quantity of first event instances, the quantity of second event instances, the maximum time length of the sequence, the minimum time gap, and the maximum time gap.

53. A system for identifying a surprise pattern within a sequence of time-stamped event instances, the system comprising:

means for storing the sequence of time-stamped event instances;

means for defining the pattern;

means for calculating an expected quantity of distinct occurrences of a pattern in the sequence;

means for determining a maximum cardinality of the pattern in the sequence; and

means for identifying the surprise pattern as a function of the estimated quantity of distinct occurrences and the maximum cardinality.

54. The system of claim 53 wherein the time-stamped event instances are events associated with an operation of an aircraft.

55. The system of claim 54 wherein the surprise pattern is indicative of a required maintenance procedure on the aircraft.

56. Computer readable medium including computer executable instructions for identifying a surprise pattern within a sequence of time-stamped event instances, the computer instructions comprising:

means for calculating an expected quantity of distinct occurrences of a pattern in the sequence;

means for determining a maximum cardinality of the pattern in the sequence; and

means for identifying the surprise pattern as a function of the estimated quantity of distinct occurrences and the maximum cardinality.