Determining similarity between event types in sequences

• US 6,526,405 B1
• Filed: 12/17/1999
• Issued: 02/25/2003
• Est. Priority Date: 12/17/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mannila, Heikki O., Moen, Pirjo
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Le, Debbie M.
• Application Number:
  US09/438,114
• Time in Patent Office: 1,166 Days
• Field of Search: 707/1-6, 707/7
• US Class Current: 719/318
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/20 Analysing
• 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

Determining a degree of relative similarity between event types in event sequences by examining the context of the event types facilitates similarity analysis of large sets of event sequences. A method for determining the similarity between event types in event sequences by examining the data log of the event sequence. A context set of event types is compiled for each event type. The context sets are then compared to determine a degree of similarity between their corresponding event types. The context sets may be compiled by recording the event types which happen within a predetermined time period of the event type in question. The context sets may then be transformed into vectors and a distance calculated between the vectors. The distance indicates a degree of relative similarity between the event types which correspond to the vectors.

Claims

1. A method for determining the similarity between a plurality of event types occurring in an event sequence, wherein the event sequence is an ordered collection of events from a set of m event types with each event having an occurrence time, comprising:

(a) compiling a set of context events for each of the plurality of event types by compiling the set of events having an occurrence time within a predetermined period prior to each occurrence of the event type;

(b) transforming each set of context events into a vector representation by constructing an m dimensional centroid vector wherein each dimension corresponds to an event type and the value of each dimension is based on the number of times the event type occurs in the set of context events; and

(c) calculating the distance between the vector representations.

2. A computer readable medium having computer executable instructions for performing steps for determining the similarity between a plurality of event types occurring in an event sequence, wherein the event sequence is an ordered collection of events from a set of m event types with each event having an occurrence time, the steps comprising:

(a) compiling a set of context events for each of the plurality of event types by compiling the set of events having an occurrence time within a predetermined period prior to each occurrence of the event type;

(b) transforming each set of context events into a vector representation by constructing an m dimensional centroid vector wherein each dimension corresponds to an event type and the value of each dimension is based on the number of times the event type occurs in the set of context events; and

(c) calculating the distance between the vector representations.