US 8,027,949 B2Granted

Constructing a comprehensive summary of an event sequence

AssigneeInternational Business Machines Corporation

InventorsGerald G. Kiernan, Evimaria Terzi

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present invention provides a method and system for constructing one or more a comprehensive summaries of event sequence(s). The present invention approaches the problem of finding the shortest yet most comprehensive summary of an event sequence by transforming this summarization problem into a concrete optimization problem and provides a computer-implementing technique for solving this optimization problem to construct and/or form the basis for constructing the summaries. The summaries describe an entire event sequence while at the same time reveal local associations between events of that sequence. In certain embodiments, the segmentation of the event sequence produced in accordance with the present invention is itself a summary of the event sequence. In other embodiments, the segmentation produced forms a basis for one or more summaries.

Claims13

Dependent claims

A computer implemented Minimum Description Length (MDL) based method for constructing a summary of an event sequence S, the method balancing between over-generalizing and over-fitting descriptions of the event sequence S, the method comprising:

receiving an event sequence S identifying events of different event types occurring over a time interval;
segmenting the event sequence S into segments (S˜, . . . , Sk), wherein k is an integer, wherein the segmenting partitions the time interval into contiguous, non-overlapping intervals, wherein the segmenting minimizing a total cost TL(S,M) in bits for describing the event sequence S, wherein the total cost TL(SgV/) in bits consists of a number of bits used to identify segment boundaries segmenting the event sequence S into segments (S˜, . . . , Sk) and a total local cost LL(Si,Mi) in bits for describing each segment, wherein the total local costs LL(Si,M˜) in bits consists of a number of bits used to identify a local model M˜ and a number of bits used to describe the corresponding segment Si using the local model Mi, and wherein each local model M˜ groups one or more events of one or more events types within the corresponding segment Si into one or more groups based on a frequency of occurrence of the events;
and
outputting a summary for the event sequence S, the summary indicating the segments (S˜, . . . , Sk) and the groups;
and
wherein the time interval is [1,n], and minimizing the total cost
TL in bits comprises computing using the following:
TL
⁡
(
S
,
M
)
=
∼
log
⁢
⁢
n
+
∑
i
=
1
k
⁢
⁢
LL
⁡
(
Si
,
M
,
)
.

34 more elements

A computer program product for constructing, based on Minimum Description Length, a summary of an event sequence S, the computer program product comprising:

a computer usable medium having computer usable program code embodied therewith, the computer usable program code comprising:
computer usable program code configured to receive an event sequence S identifying events of different event types occurring over a time interval;
computer usable program code configured to segment the event sequence S into segments (S˜, . . . , S˜), wherein k is an integer, wherein the segmenting partitions the time interval into contiguous, non-overlapping intervals, wherein the segmenting minimizing a total cost TL(S,M) in bits for describing the event sequence S, wherein the total cost TL(S,M) in bits consists of a number of bits used to identify segment boundaries segmenting the event sequence S into segments (S˜, . . . , Sk) and a total local cost LL(Si,M˜) in bits for describing each segment, wherein the total local costs LL(Si,Mi) in bits consists of a number of bits used to identify a local model Mi and a number of bits used to describe the corresponding segment S˜ using the local model M˜, and wherein each local model M˜ groups one or more events of one or more events types within the corresponding segment S˜ into one or more groups based on a frequency of occurrence of the events;
and
computer usable program code configured to output a summary for the event sequence S, the summary indicating the segments (S˜, . . . , S˜) and the groups;
and
wherein the time interval is [1,n], and minimizing the total cost
TL in bits comprises computing using the following:
TL
⁡
(
S
,
M
)
=
∼
log
⁢
⁢
n
+
∑
i
=
1
k
⁢
⁢
LL
⁡
(
Si
,
M
,
)
.

35 more elements

A system for constructing a summary of an event sequence S, the system comprising:

a database system storing an event sequence S;
memory storing computer usable program code;
and
a processor coupled to the data system to receive the event sequence S from the database system and coupled to the memory to execute the computer usable program code stored on the memory;
wherein the computer usable program code comprises:
computer usable program code configured to receive an event sequence S identifying events of different event types occurring over a time interval;
computer usable program code configured to segment the event sequence S into segments (S˜, . . . , Sk), wherein k is an integer, wherein the segmenting partitions the time interval into contiguous, non-overlapping intervals, wherein the segmenting minimizing a total cost TL(S,M) in bits for describing the event sequence S, wherein the total cost TL(S,M) in bits consists of a number of bits used to identify segment boundaries segmenting the event sequence S into segments (Sb . . . , Sk) and a total local cost LL(Si,Mi) in bits for describing each segment, wherein the total local costs LL(Si,Mi) in bits consists of a number of bits used to identify a local model M˜ and a number of bits used to describe the corresponding segment S˜ using the local model M˜, and wherein each local model M˜ groups one or more events of one or more events types within the corresponding segment S˜ into one or more groups based on a frequency of occurrence of the events;
and
computer usable program code configured to output a summary for the event sequence S, the summary indicating the segments (Sb . . . , Sk) and the groups;
and
wherein the time interval is [1,n], and minimizing the total cost
TL in bits comprises computing using the following:
TL
⁡
(
S
,
M
)
=
∼
log
⁢
⁢
n
+
∑
i
=
1
k
⁢
⁢
LL
⁡
(
Si
,
M
,
)
.

39 more elements

Dependencies are inferred from the claim text.