Method and apparatus for detecting causality

• US 5,933,821 A
• Filed: 08/28/1997
• Issued: 08/03/1999
• Est. Priority Date: 08/30/1996
• Status: Expired due to Fees

• Current Assignee: KDDI Corporation
• Original Assignee: Kokusai Denshi Denwa Company Limited (KDDI Corporation)
• Inventors: Matsumoto, Kazunori, Hashimoto, Kazuo
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/919,449
• Time in Patent Office: 705 Days
• Field of Search: 707/6, 707/7, 707/512, 707/1, 707/2, 707/3, 707/4, 707/5, 707/201, 707/202, 705/7, 273/257
• US Class Current: 1/1
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/25 Testing of logic operation, e.g. by logic analysers
• CPC Class Codes: G06F 11/34 Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A causality detection apparatus for detecting causality of events based upon a database provided with log of the events includes a sorter module for generating an event list by sorting in time sequence the events, and a frequency analysis module for calculating, based upon the event list, the number of appearance of an event set pair <X,Y> of a first event set X(={e_x1,e_x2, . . . ,e_xn, . . . }, e_xn indicates an event and n is a natural number) and a second event set Y(={e_y1,e_y2, . . . ,e_yn, . . . }, e_yn indicates an event), the number of appearance of the first event set X and the number of appearance of the second event set Y. The event set pair <X,Y> has co-occurrence so that the second event set Y occurs within a predetermined time period (window size W) after a time of occurrence of the first event set X. The apparatus further includes a causality detection module for detecting, based upon the number of appearance of the event set pair <X,Y>, upon the number of appearance of the first event set X and upon the number of appearance of the second event set Y, significance of causality caused by the first event set X to occur the second event set Y within the window size W.

Claims

1. A causality detection apparatus for detecting causality of events based upon a database provided with log of the events, comprising:

a sorter means for generating an event list by sorting in time sequence the events;

a frequency analysis means for calculating, based upon said event list, the number of appearances of an event set pair of a first event set and a second event set, the number of appearances of said first event set and the number of appearances of said second event set, said second event set occurring within a predetermined time period after a time of occurrence of said first event set; and

a causality detection means for detecting, based upon the number of appearances of said event set pair, upon the number of appearances of said first event set and upon the number of appearances of said second event set, significance of causality caused by said first event and said second event set occuring within said predetermined time period.

2. The apparatus as claimed in claim 1, wherein said frequency analysis means includes means for calculating said numbers during intermediate period between a time of occurrence of said first event set and a time of occurrence of said second event set when none of said first and second event sets is occurring.

3. The apparatus as claimed in claim 1, wherein said causality detection means includes means for calculating, with respect to each event set pair, the values of information criteria of two models based upon log likelihoods of the models and upon the number of parameters used in the models, one of said models postulating the existence of causality and the other one of said models postulating no existence of causality, and decision means for detecting significance of causality by comparing the calculated values of information criteria.

4. The apparatus as claimed in claim 3, wherein said decision means decides that there exists significance of causality when the calculated value of information criteria of the model which postulates the existence of causality is smaller than the calculated value of information criteria of the model which postulates no existence of causality.

5. The apparatus as claimed in claim 1, wherein said sorter means includes means for generating a local list which is a part of said event list, and means for generating an event list by updating in inverse time sequence said local list.

6. The apparatus as claimed in claim 1, wherein said frequency analysis means includes means for calculating the number of appearance of an event set pair <

X,Y>

of a first event set X(={e_x1,e_x2, . . . ,e_xn, . . . }, e_xn indicates an event and n is a natural number) occurred at a time t_i (i is an integer equal to or more than

     0) and a second event set Y(={e_y1,e_y2, . . . ,e_yn, . . . }, e_yn indicates an event) occurred at a time t_k (t_i <

t_k <

t_i +w, i and k are integers equal to or more than 0, w is said predetermined time period) in said event list, said event set pair <

X,Y>

satisfying a sequence condition of ∀

e_x .di-elect cons.X, e_y .di-elect cons.Y, e_z .di-elect cons.Z, e_x ≠

e_z and e_y≠

e_z with respect to said first event set X, said second event set Y and a third event set Z(={e_z1,e_z2, . . . ,e_zn, . . . }, e_zn indicates an event) occurred at an optional time t_j which satisfies t_i <

t_j <

t_k (j is an integer equal to or more than

     0), said calculation of the number of appearance of said event set pair <

X,Y>

being executed by updating a set of events NB_q occurred between a time t_p+1 and a time t_q (p<

q≦

m(p), m(p) is a natural number), and by updating a set of events H_q which satisfy said sequence condition and are contained in a fourth event set E'"'"' (={e_e1,e_e2, . . . ,e_en, . . . }, e_en indicates an event) occurred at a time t_q (p<

q<

m(p)) and in optional events at the time t_p+1, with reference to a local list which is a part of the event list (event list at times t_p, t_p+1, . . . ,t_m(p), t_m(p) <

t_p +w<

t_m(p)+1) and updated by said sorter means.

7. A causality detection apparatus for detecting causality of events based upon a database provided with log of the events, comprising:

a sorter means for generating an event list by sorting in time sequence the events;

a frequency analysis means for calculating, based upon said event list, the number of appearances of an event pair of a first event and a second event, the number of appearance of the said first event and the number of appearances of said second event, said second event occurring within a predetermined time period after a time of occurrence of said first event; and

a causality detection means for detecting, based upon the number of appearances of said event pair, upon the number of appearances of said first event and upon the number of appearances of said second event, significance of causality caused by said first event and said second event set occuring within said predetermined time period.

8. The apparatus as claimed in claim 7, wherein said frequency analysis means includes means for calculating said numbers during intermediate period between a time of occurrence of said first event and a time of occurrence of said second event when none of said first and second events is occurring.

9. The apparatus as claimed in claim 7, wherein said causality detection means includes means for calculating, with respect to each event pair, the values of information criteria of two models based upon log likelihoods of the models and upon the number of parameters used in the models, one of said models postulating the existence of causality and the other one of said models postulating no existence of causality, and decision means for detecting significance of causality by comparing the calculated values of information criteria.

10. The apparatus as claimed in claim 9, wherein said decision means decides that there exists significance of causality when the calculated value of information criteria of the model which postulates the existence of causality is smaller than the calculated value of information criteria of the model which postulates no existence of causality.

11. The apparatus as claimed in claim 7, wherein said sorter means includes means for generating a local list which is a part of said event list, and means for generating an event list by updating in inverse time sequence said local list.

12. The apparatus as claimed in claim 7, wherein said frequency analysis means includes means for calculating the number of appearance of an event pair <

e_x,e_y >

of a first event e_x occurred at a time t_i (i is an integer equal to or more than

     0) and a second event e_y occurred at a time t_k (t_i <

t_k <

t_i +w, i and k are integers equal to or more than 0, w is said predetermined time period) in said event list, said event pair <

e_x,e_y >

satisfying a sequence condition of e_x ≠

e_z and e_y ≠

e_z with respect to said first event e_x, said second event e_y and a third event e_z occurred at an optional time t_j which satisfies t_i <

t_j <

t_k (j is an integer equal to or more than

     0), said calculation of the number of appearance of said event pair <

e_x,e_y >

being executed by updating a set of events NB_q occurred between a time t_p+1 and a time t_q (p<

q≦

m(p), m(p) is a natural number), and by updating a set of events H_q which satisfy said sequence condition and are contained in a fourth event e_e occurred at a time t_q (p<

q<

m(p)) and in optional events at the time t_p+1, with reference to a local list which is a part of the event list (event list at times t_p,t_p+1, . . . ,t_m(p), t_m(p) <

t_p +w<

t_m(p)+1) and updated by said sorter means.

13. A causality detection method for detecting causality of events based upon a database provided with log of the events, said method comprising:

a sorting step of generating an event list by sorting in time sequence the events;

a frequency analysis step of calculating, based upon said event list, the number of appearances of an event set pair of a first event set and a second event set, the number of appearances of said first event set and the number of appearances of said second event set, said second event set occurring within a predetermined time period after a time of occurrence of said first event set; and

a causality detection step of detecting, based upon the number of appearances of said event set pair, upon the number of appearances of said first event set and upon the number of appearances of said second event set, significance of causality caused by said first event and said second event set occuring within said predetermined time period.

14. The method as claimed in claim 13, wherein said frequency analysis step includes a step of calculating said numbers during intermediate period between a time of occurrence of said first event set and a time of occurrence of said second event set when none of said first and second event sets is occurring.

15. The method as claimed in claim 13, wherein said frequency analysis step includes a step of calculating, with respect to each event set pair, the values of information criteria of two models based upon log likelihoods of the models and upon the number of parameters used in the models, one of said models postulating the existence of causality and the other one of said models postulating no existence of causality, and a decision step of detecting significance of causality by comparing the calculated values of information criteria.

16. The method as claimed in claim 15, wherein said decision step decides that there exists significance of causality when the calculated value of information criteria of the model which postulates the existence of causality is smaller than the calculated value of information criteria of the model which postulates no existence of causality.

17. The method as claimed in claim 13, wherein said sorting step includes a step of generating a local list which is a part of said event list, and a step of generating an event list by updating in inverse time sequence said local list.

18. The method as claimed in claim 13, wherein said frequency analysis step includes a step of calculating the number of appearance of an event set pair <

X,Y>

of a first event set X(={e_x1,e_x2, . . . ,e_xn, . . . }, e_xn indicates an event and n is a natural number) occurred at a time t_i (i is an integer equal to or more than

     0) and a second event set Y(={e_y1,e_y2, . . . ,e_yn, . . . }, e_yn indicates an event) occurred at a time t_k (t_i <

t_k <

t_i +w, i and k are integers equal to or more than 0, w is said predetermined time period) in said event list, said event set pair <

X,Y>

satisfying a sequence condition of ∀

e_x .di-elect cons.X, e_y .di-elect cons.Y, e_z .di-elect cons.Z, e_x ≠

e_z and e_y ≠

e_z with respect to said first event set X, said second event set Y and a third event set Z(={e_z1,e_z2, . . . ,e_zn, . . . }, e_zn indicates an event) occurred at an optional time t_j which satisfies t_i <

t_j <

t_k (j is an integer equal to or more than

     0), said calculation of the number of appearance of said event set pair <

X,Y>

being executed by updating a set of events NB_q occurred between a time t_p+1 and a time t_q (p<

q≦

m(p), m(p) is a natural number), and by updating a set of events H_q which satisfy said sequence condition and are contained in a fourth event set E'"'"' (={e_e1,e_e2, . . . ,e_en, . . . }, e_en indicates an event) occurred at a time t_q (p<

q<

m(p)) and in optional events at the time t_p+1, with reference to a local list which is a part of the event list (event list at times t_p,t_p+1, . . . ,t_m(p), t_m(p) <

t_p +w<

t_m(p)+1) and updated at said sorting step.

19. A causality detection method for detecting causality of events based upon a database provided with log of the events, comprising:

a sorting step of generating an event list by sorting in time sequence the events;

a frequency analysis step of calculating, based upon said event list, the number of appearances of an event pair of a first event and a second event, the number of appearance of the said first event and the number of appearance of said second event, said second event occurring within a predetermined time period after a time of occurrence of said first event; and

a causality detection step of detecting, based upon the number of appearance of said event pair, upon the number of appearances of said first event and upon the number of appearances of said second event, significance of causality caused by said first event and said second event set occuring within said predetermined time period.

20. The method as claimed in claim 19, wherein said frequency analysis step includes a step of calculating said numbers during intermediate period between a time of occurrence of said first event and a time of occurrence of said second event when none of said first and second events is occurring.

21. The method as claimed in claim 19, wherein said causality detection step includes a step of calculating, with respect to each event pair, the values of information criteria of two models based upon log likelihoods of the models and upon the number of parameters used in the models, one of said models postulating the existence of causality and the other one of said models postulating no existence of causality, and a decision step of detecting significance of causality by comparing the calculated values of information criteria.

22. The method as claimed in claim 21, wherein said decision step decides that there exists significance of causality when the calculated value of information criteria of the model which postulates the existence of causality is smaller than the calculated value of information criteria of the model which postulates no existence of causality.

23. The method as claimed in claim 19, wherein said sorting step includes a step of generating a local list which is a part of said event list, and a step of generating an event list by updating in inverse time sequence said local list.

24. The method as claimed in claim 19, wherein said frequency analysis step includes a step of calculating the number of appearance of an event pair <

e_x,e_y >

of a first event e_x occurred at a time t_i (i is an integer equal to or more than

     0) and a second event e_y occurred at a time t_k (t_i <

t_k <

t_i +w, i and k are integers equal to or more than 0, w is said predetermined time period) in said event list, said event pair <

e_x,e_y >

satisfying a sequence condition of e_x ≠

e_z and e_y ≠

e_z with respect to said first event e_x, said second event e_y and a third event e_z occurred at an optional time t_j which satisfies t_i <

t_j <

t_k (j is an integer equal to or more than

     0), said calculation of the number of appearance of said event pair <

e_x,e_y >

being executed by updating a set of events NB_q occurred between a time t_p+1 and a time t_q (p<

q m(p), m(p) is a natural number), and by updating a set of events H_q which satisfy said sequence condition and are contained in a fourth event e_e occurred at a time t_q (p<

q<

m(p)) and in optional events at the time t_p+1, with reference to a local list which is a part of the event list (event list at times t_p,t_p+1, . . . ,t_m(p), t_m(p) <

t_p +w<

t_m(p)+1) and updated at said sorting step.