Systems and methods for pairwise analysis of event data

• US 6,697,802 B2
• Filed: 10/12/2001
• Issued: 02/24/2004
• Est. Priority Date: 10/12/2001
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Grabarnik, Genady, Ma, Sheng, Perng, Chang-Shing, Hellerstein, Joseph L.
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/976,574
• Publication Number:
  US 20030097367A1
• Time in Patent Office: 865 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 709/200-218
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques for mining or discovering one or more patterns in an input data set, wherein the input data set is characterized by attributes, comprises the following steps. First, the technique includes mapping attributes of the input data set to mapping values. Then, one or more candidate patterns are formed as groupings of two mapping values that occur within a predefined time period. Next, for each of the one or more candidate patterns, a qualification function is computed and a result of the qualification function is compared with at least one predefined threshold value. The one or more candidate patterns whose qualification function results are greater than or equal to the predefined threshold value are identified as one or more qualified patterns.

Claims

1. A computer-based method of mining one or more patterns in an input data set, the input data set being characterized by attributes, the method comprising the steps of:

mapping attributes of the input data set to mapping values; and

forming one or more candidate patterns as groupings of two mapping values that occur within a predefined time period;

for each of the one or more candidate patterns;

computing a qualification function;

comparing a result of the qualification function with at least one predefined threshold value; and

identifying the one or more candidate patterns whose qualification function results are one of greater than and equal to the at least one predefined threshold value as one or more qualified patterns.

2. The method of claim 1, wherein the mapping step comprises:

mapping attributes of at least two types associated with the input data set to item values; and

forming one or more candidate patterns as groupings of two item values that occur within a predefined time period.

3. The method of claim 2, wherein the input data set comprises event data.

4. The method of claim 3, wherein the at least two attribute types are an event type and an event source identifier.

5. The method of claim 1, wherein the mapping step comprises:

mapping attributes of at least one type associated with the input data set to item values, and mapping attributes of at least another type associated with the input data set to key values; and

forming one or more candidate patterns as groupings of two item values that are associated with the same key value and occur within a predefined time period.

6. The method of claim 5, wherein the input data set comprises event data.

7. The method of claim 6, wherein the at least one attribute type is an event type and the at least another attribute type is an event source identifier.

8. The method of claim 1, wherein the qualification function comprises one or more significance measurements.

9. The method of claim 8, wherein the one or more significance measurements comprise at least one of an occurrence count, a predictive power measure, a mutual dependence measure, a correlation score, and a chi-squared score.

10. The method of claim 1, wherein at least one of the mapping values, qualification function, and the threshold value are specified by a user.

11. The method of claim 1, further comprising the step of providing one or more visualizations of the one or more qualified patterns.

12. The method of claim 11, wherein the one or more visualizations comprise one or more graphical representations of the qualified patterns.

13. The method of claim 12, wherein a graphical representation of a qualified pattern comprises nodes representing one of the attributes of the input data set and a link connecting the nodes representing that the nodes form a qualified pattern.

14. The method of claim 13, wherein the link is visually encoded to represent the result of the qualification function.

15. The method of claim 1, wherein the node is visually encoded to represent a measure associated with a corresponding attribute of the input data set.

16. The method of claim 1, further comprising the step of summarizing qualified patterns to reveal multi-item relationships.

17. The method of claim 16, wherein the summarizing step comprises grouping qualified patterns having at least one identical mapping value into a group.

18. The method of claim 16, wherein the summarizing step comprises merging qualified patterns into one or more higher order patterns.

19. Apparatus for mining one or more patterns in an input data set, the input data set being characterized by attributes, the apparatus comprising:

at least one processor operative to;

(i) map attributes of the input data set to mapping values;

(ii) form one or more candidate patterns as groupings of two mapping values that occur within a predefined time period;

(iii) for each of the one or more candidate patterns;

compute a qualification function, and compare a result of the qualification function with at least one predefined threshold value; and

(iv) identify the one or more candidate patterns whose qualification function results are one of greater than and equal to the at least one predefined threshold value as one or more qualified patterns; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the one or more qualified patterns.

20. The apparatus of claim 19, wherein the mapping operation comprises:

mapping attributes of at least two types associated with the input data set to item values; and

forming one or more candidate patterns as groupings of two item values that occur within a predefined time period.

21. The apparatus of claim 19, wherein the mapping operation comprises:

mapping attributes of at least one type associated with the input data set to item values, and mapping attributes of at least another type associated with the input data set to key values; and

forming one or more candidate patterns as groupings of two item values that are associated with the same key value and occur within a predefined time period.

22. The apparatus of claim 19, wherein the qualification function comprises one or more significance measurements.

23. The apparatus of claim 19, wherein the at least one processor is further operative to provide one or more visualizations of the one or more qualified patterns.

24. The apparatus of claim 19, further comprising the step of summarizing qualified patterns to reveal multi-item relationships.

25. An article of manufacture for mining one or more patterns in an input data set, the input data set being characterized by attributes, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

mapping attributes of the input data set to mapping values; and

forming one or more candidate patterns as groupings of two mapping values that occur within a predefined time period;

for each of the one or more candidate patterns;

computing a qualification function;

comparing a result of the qualification function with at least one predefined threshold value; and

identifying the one or more candidate patterns whose qualification function results are one of greater than and equal to the at least one predefined threshold value as one or more qualified patterns.