# US 2010/0251210 A1 · Mining sequential patterns in weighted directed graphs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0251210 A1
- Document ID: US20100251210A1
- Status: Published application
- Kind: A1
- Application number: 12/410,460
- Filed: 2009-03-24
- Published: 2010-09-30
- Earliest claimed: 2009-03-24
- Assignees: International Business Machines Corporation
- Inventors: Jose Nelson Amaral; Adam Paul Jocksch; Marcel Mitran
- Web page: https://patentgrep.com/patent/US20100251210A1

## CPC

- G06F 11/3604: Analysis of software for verifying properties of programs (testing of software G06F11/3668)
- G06F 11/3616: {using software metrics}
- G06F 11/3452: {Performance evaluation by statistical analysis}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for finding sequential patterns of attributes in a directed graph includes constructing a directed graph comprising multiple nodes and edges between the nodes. Each of the nodes may be assigned one or more attributes. Similarly, each of the edges may be assigned a weight value which may indicate the probably the edge will be traversed during traversal of the directed graph. The method may further include finding sequences of attributes in the directed graph that have some minimum amount of frequency and/or time support. In performing this step, the frequency support of each individual instance of a sequence of attributes may be calculated by multiplying the weight values along the edge or edges of the instance. A corresponding apparatus and computer program product are also disclosed and claimed herein.

## Claims

### Claim 1

A method for finding sequential patterns of attributes in a directed graph, the method comprising:
(a) constructing a directed graph comprising a plurality of nodes and a plurality of edges between the nodes;
(b) assigning at least one attribute to each of the nodes;
(c) assigning a weight value to each of the edges; and
(d) finding sequences of attributes in the directed graph that have some minimum amount of frequency support, wherein the frequency support of each individual instance of a sequence of attributes is calculated by multiplying the weight values along the edges of the instance.

### Claim 2 (depends on 1)

The method of claim 1, wherein (d) finding sequences of attributes in the directed graph that have some minimum amount of frequency support comprises the following:
(e) creating a first generation G1 of candidate sequences constructed from the union of each individual attribute;
(f) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn;
(g) discarding all candidate sequences where the sequence frequency support value does not satisfy a frequency support threshold;
(h) creating a next generation Gn+1 of candidate sequences from the surviving candidate sequences from step (g); and
(i) repeating steps (f), (g), and (h) until one of the following occurs: a selected number of generations has been completed and no sequence frequency support value satisfies the frequency support threshold.

### Claim 3 (depends on 2)

The method of claim 2, wherein (f) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn includes performing the following:
(1) finding all instances of the candidate sequence in the directed graph;
(2) for each instance of the candidate sequence, calculating an instance frequency support value by multiplying the weight values along the edges of the instance; and
(3) summing the instance frequency support values calculated in step (b) to yield the sequence frequency support value.

### Claim 4 (depends on 1)

The method of claim 1, wherein the directed graph comprises at least one of a branch, a join point, and a cycle.

### Claim 5 (depends on 1)

The method of claim 1, where the directed graph is a control flow graph of a computer program.

### Claim 6 (depends on 5)

The method of claim 5, wherein each node represents one of an opcode, bytecode, instruction, method, and block of instructions in a computer program.

### Claim 7 (depends on 6)

The method of claim 6, wherein, each attribute describes the characteristics of one of an opcode, bytecode, instruction, method, and group of instructions.

### Claim 8 (depends on 1)

The method of claim 1, wherein each weight value represents the probability the edge will be traversed when traversing the directed graph.

### Claim 9 (depends on 1)

The method of claim 1, further comprising finding sequences of attributes in the directed graph that have some minimum amount of time support.

### Claim 10 (depends on 9)

The method of claim 9, further comprising calculating the time support by aggregating tick counts for each sequence of attributes in the directed graph.

### Claim 11

An apparatus comprising a data mining module configured to find sequential patterns of attributes in a directed graph, the data mining module configured to:
(a) construct a directed graph comprising a plurality of nodes and a plurality of edges between the nodes;
(b) assign at least one attribute to each of the nodes;
(c) assign a weight value to each of the edges; and
(d) find sequences of attributes in the directed graph that have some minimum amount of frequency support, wherein the frequency support of each individual instance of a sequence of attributes is calculated by multiplying the weight values along the edges of the instance.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein (d) finding sequences of attributes in the directed graph that have some minimum amount of frequency support comprises the following:
(e) creating a first generation G1 of candidate sequences constructed from the union of each individual attribute;
(f) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn;
(g) discarding all candidate sequences where the sequence frequency support value does not satisfy a frequency support threshold;
(h) creating a next generation Gn+1 of candidate sequences from the surviving candidate sequences from step (g); and
(i) repeating steps (f), (g), and (h) until one of the following occurs: a selected number of generations has been completed and no sequence frequency support value satisfies the frequency support threshold.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein (f) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn includes performing the following:
(1) finding all instances of the candidate sequence in the directed graph;
(2) for each instance of the candidate sequence, calculating an instance frequency support value by multiplying the weight values along the edges of the instance; and
(3) summing the instance frequency support values calculated in step (b) to yield the sequence frequency support value.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein the directed graph comprises at least one of a branch, a join point, and a cycle.

### Claim 15 (depends on 11)

The apparatus of claim 11, where the directed graph is a control flow graph of a computer program.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein each node represents one of an opcode, bytecode, instruction, method, and block of instructions in a computer program.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein, each attribute describes the characteristics of one of an opcode, bytecode, instruction, method, and group of instructions.

### Claim 18 (depends on 11)

The apparatus of claim 11, wherein each weight value represents the probability the edge will be traversed when traversing the directed graph.

### Claim 19 (depends on 11)

The apparatus of claim 11, wherein the mining module is further configured to find sequences of attributes in the directed graph that have some minimum amount of time support.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the mining module is further configured to calculate the time support by aggregating tick counts for each sequence of attributes in the directed graph.

### Claim 21

A computer program product for finding sequential patterns of attributes in a directed graph, the computer program product comprising a computer-usable medium having computer-usable program code embodied therein, the computer-usable program code comprising:
computer-usable program code to (a) construct a directed graph comprising a plurality of nodes and a plurality of edges between the nodes;
computer-usable program code to (b) assign at least one attribute to each of the nodes;
computer-usable program code to (c) assign a weight value to each of the edges; and
computer-usable program code to (d) find sequences of attributes in the directed graph that have some minimum amount of frequency support, wherein the frequency support of each individual instance of a sequence of attributes is calculated by multiplying the weight values along the edges of the instance.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein (d) finding sequences of attributes in the directed graph that have some minimum amount of frequency support comprises the following:
(e) creating a first generation G1 of candidate sequences constructed from the union of each individual attribute;
(f) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn;
(g) discarding all candidate sequences where the sequence frequency support value does not satisfy a frequency support threshold;
(h) creating a next generation Gn+1 of candidate sequences from the surviving candidate sequences from step (g); and
(i) repeating steps (f), (g), and (h) until one of the following occurs: a selected number of generations has been completed and no sequence frequency support value satisfies the frequency support threshold.

### Claim 23 (depends on 22)

The computer program product of claim 22, wherein (f) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn includes performing the following:
(1) finding all instances of the candidate sequence in the directed graph;
(2) for each instance of the candidate sequence, calculating an instance frequency support value by multiplying the weight values along the edges of the instance; and
(3) summing the instance frequency support values calculated in step (2) to yield the sequence frequency support value.

### Claim 24

A method for finding sequential patterns of attributes in a directed graph, the method comprising:
(1) constructing a directed graph comprising a plurality of nodes and a plurality of edges connecting the nodes;
(2) assigning at least one attribute to each of the nodes;
(3) assigning a weight value to each of the edges;
(4) creating a first generation G1 of candidate sequences constructed from the union of each individual attribute;
(5) calculating a sequence frequency support value for each candidate sequence of attributes in the current generation Gn by performing the following:
(a) finding all instances of the candidate sequence in the directed graph;
(b) for each instance of the candidate sequence, calculating an instance frequency support value by multiplying the weight values along the edges of the instance; and
(c) summing the instance frequency support values calculated in step (b) to yield the sequence frequency support value;
(6) discarding all candidate sequences where the sequence frequency support value does not satisfy a support threshold;
(7) creating a next generation Gn+1 of candidate sequences from the surviving candidate sequences from step (6); and
(8) repeating steps (5), (6), and (7) until one of the following occurs: a selected number of generations has been completed and no sequence frequency support value satisfies the support threshold.
