Method and system for finding evolving regions in graphs without persistent node identity

• US 20070016898A1
• Filed: 07/13/2005
• Published: 01/18/2007
• Est. Priority Date: 07/13/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Poddar, Indrajit, Mitchell, Nicholas, Derby, Herbert
• Granted Patent: US 7,233,733 B2
• Time in Patent Office: Days
• US Class Current: 717/144
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589

Abstract

A system, method, and computer program for identifying evolving regions in a graph of interrelated nodes representing a computer system environment. The method includes generating a series of samples (302) of the environment. Each sample includes a plurality of interrelated nodes (502) and at least one edge (504) classified into a plurality of at least one of node type and edge type, respectively. A summary (900) of the plurality of at least one of node type (502) and edge type (504) is created for the series of samples (302). A summary instance (312) of the summary (900) is created for each sample. At least one summary instance (312) is compared to at least one subsequent summary instance (314) and at least one result (318) is stored in memory (106). A successive behavior is characterized for one or more of the at least one of the node type and the edge type.

Claims

1. A method for identifying at least one evolving region in a graph of interrelated nodes representing an evolving computer system environment, the method using an information processing system comprising:

generating a series of samples of an evolving computer system environment, each sample in the series of samples including a plurality of interrelated nodes and at least one edge classified into a plurality of at least one of a node type and an edge type, respectively;

creating a summary of the plurality of interrelated nodes and at least one edge in the series of samples, the summary summarizing at least one of all node types and all edge types in the series of samples;

creating an instance of the summary for each sample by summarizing at least one of all of the node types and the edge types for each sample in the series;

storing at least one instance of the created instances of the summary;

comparing at least one instance of the summary to at least one subsequent instance of the summary;

storing at least one result from comparing the instances of the summary; and

associating at least one sample of the evolving computer system environment with the at least one stored comparison result to characterize a successive behavior of the evolving computer system environment for one or more of the at least one of the node type and the edge type.

2. The method of claim 1, further comprising:

determining at least one pattern, based on the successive behavior which has been characterized for the one or more of the at least one of the node type and the edge type, that estimates how at least one region in the evolving computer system environment comprising the plurality of interrelated nodes is evolving.

3. The method of claim 2, wherein the determining at least one pattern further comprises:

finding a border, in the series of samples, between nodes of a first category that are non-evolving and nodes of a second category that are at least one of possibly evolving and evolving.

4. The method of claim 2, further comprising:

determining additional patterns in a neighborhood around a node identified as a maybe-grower.

5. The method of claim 2, further comprising:

generating at least two analysis samples of the evolving computer system environment;

matching the at least one pattern against each analysis sample, wherein the matching further comprises;

relating at least two attributes of matches in the analysis sample being matched against the at least one pattern; and

determining a match relation for the analysis sample being matched with the at least one pattern;

determining, based on the match relation for each matched analysis sample and pattern, at least one evolutionary property for a region in the evolving computer system environment; and

reporting, to a user, a set of patterns displaying the determined evolutionary property which has been determined for a corresponding region in the evolving computer system environment.

6. The method of claim 1, further comprising:

categorizing at least one the node types and edge types, based on the successive behavior which has been characterized for the one or more of the at least one of the node type and the edge type, as one of a non-grower, a maybe-grower, and a definite-grower.

7. The method of claim 1, further comprising:

analyzing at least two nodes in a sample of the evolving computer system environment;

locating a set of nodes that are related to each other;

identifying related nodes as being correlated if every instance of a first related node points to a second related node in every sample of the computer system environment.

8. The method of claim 1, wherein the evolving computer system environment is one of:

a memory usage in an executing program;

a computational resource in an executing program; and

a computational resource in a computer network.

9. The method of claim 1, wherein the summary is one of:

a histogram by node type; and

a histogram by edge-type.

10. An information processing system used for estimating how regions in a graph of interrelated nodes representing an evolving computer system environment are evolving, the information system comprising:

a memory;

an information processing unit communicatively coupled to the memory;

an environment analyzing tool communicatively coupled to the memory and the information processing unit, the environment analyzing tool comprising;

a sample generator for generating a series of samples of an evolving computer system environment, wherein at least one sample in the series is stored in the memory;

a node classifier for classifying a plurality of interrelated nodes in each of the samples into a plurality of at least one of a node type and an edge type;

a summarizer for creating a summary of the plurality of interrelated nodes and at least one edge for the series of samples, wherein the summary is stored in the memory;

a comparator for comparing at least one instance of the summary to at least one subsequent instance of the summary; and

a pattern generator for determining at least one pattern of evolution of at least one region in the evolving computer system environment based on at least the summary of the plurality of interrelated nodes and the at least one edge for the series of samples.

11. The information processing system of claim 10, wherein the environment analyzing tool further comprises:

a reporter for reporting the at least one pattern of evolution to a user.

12. The information processing system of claim 10, wherein the evolving computer system environment is at least one of:

a memory usage in an executing program;

a computational resource in an executing program;

a computational resource in a computer network.

13. The information processing system of claim 10, wherein the summary is one of:

a histogram by node type; and

a histogram by edge-type.

14. The information processing system of claim 10, wherein the environment analyzing tool further comprises:

a pattern matcher for matching the at least one pattern against at least two analysis samples, the pattern matcher determining a match relation for the analysis sample being matched with the at least one pattern for identifying at least one evolutionary property for a region in the evolving computer system environment.

15. A computer readable medium including computer instructions for identifying at least one evolving region in a graph of interrelated nodes representing an evolving computer system environment, the computer readable medium comprising computer instructions for:

generating a series of samples of an evolving computer system environment, each sample in the series of samples including a plurality of interrelated nodes and at least one edge classified into a plurality of at least one of a node type and an edge type, respectively;

creating a summary of the plurality of interrelated nodes and at least one edge in the series of samples, the summary summarizing at least one of all node types and all edge types in the series of samples;

creating an instance of the summary for each sample by summarizing at least one of all of the node types and the edge types for each sample in the series;

storing at least one instance of the created instances of the summary;

comparing at least one instance of the summary to at least one subsequent instance of the summary;

storing at least one result from comparing the instances of the summary; and

associating at least one sample of the evolving computer system environment with the stored comparison results to characterize a successive behavior of the evolving computer system environment for one or more of the at least one of the node type and the edge type.

16. The computer readable medium of claim 15, further comprising instructions for:

determining at least one pattern, based on the successive behavior which has been characterized for the one or more of the at least one of the node type and the edge type, that estimates how at least one region in the evolving computer system environment comprising the plurality of interrelated nodes is evolving.

17. The computer readable medium of claim 16, wherein the determining at least one pattern instructions further comprises instructions for:

finding a border, in the series of samples, between nodes of a first category that are non-evolving and nodes of a second category that are at least one of possibly evolving and evolving.

18. The computer readable medium of claim 16, further comprising instructions for:

determining additional patterns in a neighborhood around a node identified as a maybe-grower.

19. The computer readable medium of claim 16, further comprising instructions for:

generating at least two analysis samples of the evolving computer system environment;

matching the at least one pattern against each analysis sample, wherein the matching further comprises;

relating at least two attributes of matches in the analysis sample being matched against the at least one pattern; and

determining a match relation for the analysis sample being matched with the at least one pattern;

determining, based on the match relation for each matched analysis sample and pattern, at least one evolutionary property for a region in the evolving computer system environment; and

reporting, to a user, a set of patterns displaying the determined evolutionary property which has been determined for a corresponding region in the evolving computer system environment.

determining at least one pattern, based on the successive behavior which has been characterized for the one or more of the at least one of the node type and the edge type, that estimates how at least one region in the evolving computer system environment comprising the plurality of interrelated nodes is evolving.

20. The computer readable medium of claim 15, further comprising instructions for:

categorizing at least one of the node types and edge types, based on the successive behavior which has been characterized for the one or more of the at least one of the node type and the edge type, as one of a non-grower, a maybe-grower, and a definite-grower.