Identification of performance bottlenecks

Embodiments are directed to identifying, by an apparatus comprising a processing device, a pattern in a graph that has a support value greater than a threshold, wherein: the graph comprises a plurality of weighted nodes coupled to one another by one or more weighted edges, and each of the plurality of nodes is associated with at least one weighted attribute.

BACKGROUND

The present disclosure relates generally to analysis of program efficiency, and more specifically, to an identification of performance bottlenecks.

A bottleneck is a region of a program (e.g., program code) where significant execution time is spent. Typically, software developers use a profiling tool to collect program execution profiles such as the timing information for each method, routine, process, etc. With the help of such a profiling tool, the developer can sort, e.g., methods by the time spent on them. The methods that consume an amount of time greater than a threshold defined by, e.g., the developer may be treated as bottlenecks. However, the effectiveness of this approach depends on the program's runtime characteristics. Many programs, such as large enterprise commercial applications, do not have obvious bottlenecks. Therefore, their profiles contain a large amount of routines, processes, or methods where the execution time is spent relatively evenly (e.g., within a threshold). This type of profile is often referred to as a “flat profile” because no method dominates the execution time.

Prior technologies fail to totally solve the problem of identifying bottlenecks in flat profiles. For example, prior technologies are unable to detect potential bottlenecks in the form of a sub-graph, i.e., multiple sequential paths breaching from a single entry node. Prior technologies take a long time to complete mining when processing large profile data.

SUMMARY

An embodiment is directed to a method comprising: identifying, by an apparatus comprising a processing device, a pattern in a graph that has a support value greater than a threshold, wherein: the graph comprises a plurality of weighted nodes coupled to one another by one or more weighted edges, and each of the plurality of nodes is associated with at least one weighted attribute.

An embodiment is directed to a computer program product for identifying bottlenecks, the computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code executable by a computer to perform a method comprising: identifying a pattern in a graph that has a support value greater than a threshold, wherein: the graph comprises a plurality of weighted nodes coupled to one another by one or more weighted edges, and each of the plurality of nodes is associated with at least one weighted attribute.

An embodiment is directed to an apparatus comprising: at least one processor, and memory having instructions stored thereon that, when executed by the at least one processor, cause the apparatus to: construct an execution flow graph (EFG) representative of an execution of a computer program, mine for 0-edge sub-graph patterns in the EFG that have support values that exceed a threshold, insert the 0-edge sub-graph patterns and respective instances of the 0-edge sub-graph patterns into a first data structure and a second data structure, and insert a string representation of the 0-edge sub-graph patterns into a third data structure.

DETAILED DESCRIPTION

The appendix included towards the end of this disclosure provides definitions for a number of terms that are used throughout herein.

In accordance with various embodiments of the disclosure, supported patterns may be discovered in one or more attributed flow graphs. A flow graph may include weights or values with respect to attributes, nodes, and/or edges. In some embodiments, the discovery may be obtained in connection with an execution of a program, such as a computer program. In some embodiments, a level of support for a pattern may be determined based on an analysis of a frequency associated with one or more nodes and/or edges.

In some embodiments, execution patterns (e.g., frequent execution patterns) may be identified as potential or candidate performance bottlenecks in the form of sub-graphs.

In some embodiments, a mining technique (e.g., a sub-graph mining technique) may be applied on program execution profiles (e.g., flat program execution profiles) represented as a set of execution flow graphs (EFGs).

In some embodiments, the types of patterns found may be extended from sequential patterns only (found in sub-paths of EFGs) to patterns composed of multiple paths (found in sub-graphs of EFGs).

In some embodiments, a labeling system may be constructed to uniquely identify sub-graphs.

In some embodiments, pattern registration may be used to solve pattern growth challenge(s). For example, pattern registration techniques may be used to keep or maintain a list of where nodes in a graph occur or appear for purposes of pattern expansion. Such a list may be used to expand, e.g., a single node to two nodes by facilitating a search of nodes referenced in the list. In this manner, each node might not be examined repeatedly during a growth or expansion process. For example, the list may provide for merely checking the neighbors of nodes referenced in the list.

In some embodiments, a mapping may be constructed from execution patterns to instances in application code. In some embodiments, one or more execution patterns and/or the instance(s) in the application code responsible for generating the execution pattern(s) may be provided as output. In some embodiments, a compiler may use the output to determine whether attributes or a particular flow is desirable or appropriate. In some embodiments, the compiler may use the output to obtain a more efficient program realization or execution sequence.

In some embodiments, frequent sub-graph and/or sequential execution patterns may be identified as potential performance bottlenecks. Aspects of the disclosure may improve the speed or efficiency of mining relative to other techniques via the use of a pattern registration technique and via the use and identification of characteristics of an EFG. Aspects of the disclosure may be used by, e.g., software developers. In some embodiments, program code that is an instance of a discovered pattern may be located using, e.g., a mapping system.

It is noted that various connections are set forth between elements in the following description and in the drawings. It is noted that these connections in general and, unless specified otherwise, may be direct or indirect and that this specification is not intended to be limiting in this respect. In this respect, a coupling of two entities may refer to a direct connection or an indirect connection, and may include an intervening entity.

Referring toFIG. 1, an exemplary system architecture100is shown. The architecture100is shown as including a memory102. The memory102may store executable instructions. The executable instructions may be stored or organized in any manner. As an example, at least a portion of the instructions are shown inFIG. 1as being associated with a first thread104aand a second thread104b, although any number of threads may be included. The instructions stored in the memory102may be executed by one or more processors, such as a processor106.

The threads104aand104bmay be associated with a resource108. For example, the resource108may include one or more pages, which may be organized as one or more blocks, objects, fields, strings, elements, or the like. The threads104aand104bmay access the resource108concurrently (e.g., concurrently in terms of time or space), such that the resource108may be, or include, a shared resource. In some embodiments, the resource108may include one or more input/output (I/O) devices, such as a keyboard, a mouse, a button, a switch, a trackball, a display screen, etc.

In some embodiments, one or more of the entities shown inFIG. 1may be replicated. For example, in some systems, multiple computing devices may access the resource108. In some embodiments, the computing devices may be coupled to one another via one or more networks, such as the Internet.

Turning now toFIG. 2, an example of a node200is shown. The node200may be associated with an execution flow graph (EFG).

The node200may include, or be associated with, one or more characteristics or parameters. For example, a parameter202may be indicative of a weight associated with the node200. The weight202may reflect time spent executing the node, optionally in terms of clock cycles or ticks. In the example shown inFIG. 2, the node200has a weight202equal to fifty (50).

A parameter204may be indicative of an edge frequency associated with the node. The edge frequency204may be indicative of how often the node200is executed. In the context of an EFG, the edge frequency204may be indicative of how many times the node200is entered from one or more other nodes.

A parameter206may serve as a label for the node200. The label206may include a unique identifier for the node200. The label206may be represented in different formats. For example, string or alphanumeric formats may be used for the label206in some embodiments. In the example shown inFIG. 2, the label of node200is a symbol referred to by the notation ‘L(v)’.

The node200may be associated with one or more attributes208. The attributes may be used to characterize the node200and may include one or more values. In the example shown inFIG. 2, the node200is associated with attributes208‘a’ and ‘b’, where the attribute ‘a’ has a value often (10) and the attribute ‘b’ has a value of twenty (20). The attributes208may be selected from a set or pool of attributes210. In the example shown inFIG. 2, the set of attributes210includes attributes ‘a’, ‘b’, ‘c’, and ‘d’.

FIG. 3depicts an exemplary dataset of EFGs. Specifically,FIG. 3depicts an EFG302and an EFG304. The EFG302may include nodes v1, v2, v3, v4, and v5. The node v1may be coupled to the node v2. The node v1may be coupled to the node v3. The node v2may be coupled to the node v4. The node v3may be coupled to the node v4. The node v4may be coupled to the node v5. The coupling of the nodes v1-v5may be based on one or more edges (e.g., edge204ofFIG. 2), with frequencies as shown inFIG. 3.

The node v1may have ‘a’ and ‘b’ as attributes. The node v2may have ‘b’ as an attribute. The node v3may have ‘b’ and ‘d’ as attributes. The node v4may have ‘a’ as an attribute. The node v5may have ‘b’ as an attribute. The values for the attributes with respect to the nodes v1-v5may be as shown in parenthesesFIG. 3.

The EFG304may include nodes v6, v7, v8, and v9. The node v6may be coupled to the node v7. The node v6may be coupled to the node v8. The node v7may be coupled to the node v9. The node v8may be coupled to the node v9. The coupling of the nodes v6-v9may be based on one or more edges (e.g., edge204ofFIG. 2), with frequencies as shown inFIG. 3.

The node v6may have ‘a’ and ‘c’ as attributes. The node v7may have ‘b’ as an attribute. The node v8may have ‘d’ as an attribute. The node v9may have ‘a’ and ‘c’ as attributes. The values for the attributes with respect to the nodes v6-v9may be as shown in parentheses inFIG. 3.

Taking the EFGs302and304together, a total weight may be calculated as a sum of weights of all the nodes. Thus, the total weight for the nodes v1-v9may be equal to: 30+10+20+20+20+10+20+10+10=150. Similarly, a total frequency may be calculated as a sum of the frequencies of all the edges. Thus, the total frequency for the EFGs302and304may be equal to: 10+4+6+4+6+10+14+7+6+7+6=80.

The EFGs302and304may include a number of sub-graph patterns. A sub-graph pattern may be sequential (represented as a sub-path of the EFG) or may contain split and join nodes. A sub-graph pattern may be deemed frequent if its support value exceeds a threshold. In some embodiments, the threshold may be defined or selected by a user. The support value of a pattern may correspond to a maximum of its time support (e.g., weight) and frequency.

Turning now toFIG. 4, an example of a sub-graph pattern402is shown. The sub-graph pattern402has attributes {a, b}. A mining process may be applied to identify instances in the dataset of EFGs302and304that include the sub-graph pattern402. As shown inFIG. 4, four instances (instance0, instance1, instance2, and instance3) may be identified in the EFGs302and304as including the sub-graph pattern402.

In order to calculate S_w(g), the time (node weight) support value of the sub-graph pattern402, the weight of the attribute with minimum weight may be selected in each of the instances of the sub-graph pattern402found in the dataset. According to the example shown inFIG. 4, that would be: min_w(instance0)=2 (from b), min_w(instance1)=5 (from b), min_w(instance2)=4 (from b), min_w(instance3)=3 (from a).

It is noted that, in instance3of the sub-graph pattern402, the actual minimum attribute weight is 1, belonging to attribute ‘c’. However, ‘c’ is not part of the attributes of the sub-graph pattern402, and as a consequence, it is not included in the calculation. After obtaining the minimum attribute weights for every instance of the sub-graph pattern402, they may be added to obtain S_w(g):
S—w(g)=min—w(instance0)+min—w(instance1)+min—w(instance2)+min—w(instance3)=2+5+4+3=14.

Likewise, to obtain S_f(g) the minimum edge frequencies of all instances of the sub-graph pattern402may be added:
min—f(instance0)=4, min—f(instance1)=6, min—f(instance2)=10, min—f(instance3)=7.
S—f(g)=min—f(instance0)+min—f(instance1)+min—f(instance2)+min—f(instance2)+min—f(instance3)=4+6+10+7=27.

The final support value S_m(g) of the sub-graph pattern402may be calculated as the maximum between S_w(g) and S_f(g): S_m(g)=max {S_w(g), S_f(g)}. In the example shown inFIG. 4, the final support value S_m(g) would be equal to S_f(g)=27.

In some embodiments, one or more of the time (node weight) support value S_w(g), the frequency (edge weight) support value S_f(g), and the final support value S_m(g) may be normalized to facilitate comparison with, e.g., a threshold value as described further below.

Turning now toFIG. 5, a flow graph of a method500is shown. The method500may be used to generate and provide an output set of frequent sub-graph patterns associated with one or more dataset EFGs.

The method500may start in block502, and flow may proceed from block502to block504. In block504, one or more EFGs may be constructed. For example, a set of EFGs, denoted as DS, may be constructed from profile data.

From block504, flow may proceed to block506. In block506, mining for 0-edge sub-graph patterns may be performed. These patterns in the dataset may satisfy the following conditions: 1) are composed of a single node each, 2) have a combination of one or more of the attributes present in InitialAttributeList, and 3) are frequent. The generation of such patterns may work by considering that every node created may carry a distinct set of attributes. Initially, the attributes may come from InitialAttributeList, which may be a list that contains distinct attributes that are selected as being of interest. A node may be created for every distinct attribute in the list. Then the nodes may be mined using a Sub-graph pattern mining technique (described further below). Those nodes that are frequent may have their attributes combined to generate additional nodes with sets of two distinct attributes each. The new nodes may also be mined for, and those that are found to be frequent are used to generate other nodes with sets of three distinct attributes each, and so on, until no nodes with a certain size of attribute set (in number of attributes) are frequent.

After 0-generation of patterns are discovered, the method500may populate one or more data structures to keep track of these patterns and prepare for pattern growth. For example, in block508the 0-edge sub-graph patterns and respective instances may be inserted into a data structure OutputSet. OutputSet may correspond to a set of frequent sub-graph patterns identified by the method500. As part of block508, the 0-edge sub-graph patterns and respective instances may be inserted into the end of Q. Q may be a data structure, such as a queue, that holds frequent sub-graph patterns that may be extended.

In block510, string representations of the 0-edge sub-graph patterns may be inserted into a frequent sub-graph pattern label table H. H may correspond to a data structure, such as a hash-table, that holds the string representation (described further below) of frequent sub-graph patterns. H may be used to lookup whether a pattern has already been mined for.

Distinct attributes present in the 0-generation patterns may be saved in a CurrentAttributeList. Such attributes may be used to compose candidate patterns for the next generation of patterns (e.g., 1-generation).

Blocks514-532may be indicative of sub-graph pattern growth activity. One or more of the block514-532may be used to extend one or more patterns in Q to generate child sub-graph patterns.

As an example, a first pattern in Q, which may be referred to as g, may be selected (e.g., based on a flow from block512to block520, and from block520to block522). An extension of g (e.g., block524) may be obtained by generating candidate patterns that are spanned by attaching to g a new node, connected to g by a new edge. In order to do that, a choice may be made, among the nodes in g, of a pivot node to which the new node will be connected, and then the new node and edge may be generated. Every node of g may be used once as a pivot node for candidate generation. New nodes may be generated similarly for the 0-edge sub-graphs. Instead of InitialAttributeList, however, CurrentAttributeList may be used. In order to create a candidate sub-graph pattern, each attribute in CurrentAttributeList may be associated to a new node, which may be connected to g to generate new candidate patterns g′. Every new candidate pattern g′ may then be mined for in the DS using a sub-graph pattern technique (described further below). If g′ is frequent, g′ may be inserted into a set C of frequent children of g. Otherwise, g′ may be discarded.

When all frequent child patterns of g that contain one attribute each have been placed into C, their attribute sets may be combined to generate new nodes that have two distinct attributes each. The new nodes may then be connected to g and the spanned candidate patterns may be mined for in the dataset. Those that are frequent may be placed into C (e.g., block524), and their attribute sets of size two (in number of attributes) may again be combined to generate nodes with three attributes each. This process may repeat, with increments in the number of distinct attributes associated with the new nodes, until no more candidate patterns are found to be frequent.

The other way by which sub-graph pattern g may be extended (e.g., block524) is the addition of a new edge that connects two already existing nodes in g. All nodes of g may be used as a pivot node and target node for such edge additions, but there might be no repeated edges in the new candidate sub-graph patterns generated by the additions. Every candidate pattern generated may be mined for in the dataset, and if frequent, may be inserted into C. Otherwise, the candidate may be discarded.

Every time a child sub-graph pattern is generated, it may be mined for in the dataset. Those children of g that are frequent, if any, may be inserted into the end of Q, into H, and then placed into OutputSet, along with identifiers for all the instances of such children (e.g., block532). Pattern g may then be removed from Q. The sub-graph pattern growth process may be repeated by taking the next pattern in Q. The child patterns of g might only be extended after all sub-graph patterns that have the same size as g are, themselves, extended. In other words, the patterns in the (k+1)-generation might only be extended after all patterns in the k-generation are extended. When all patterns in the k-generation are extended, CurrentAttributeList may be emptied of its contents, which were all the distinct attributes present in the patterns of the (k−1)-generation, and filled with all the distinct attributes found in the patterns of the k-generation that has just been processed. CurrentAttributeList may serve to compose the candidate patterns for the (k+1)-generation.

When Q is finally empty (e.g., the “Yes” block514out of decision block512executes) and the loop associated with blocks512,520,522,524,526,528,530, and532is finished, the method500has as its output all patterns in OutputSet (e.g., block516) and the identifiers of each of the instances where the patterns were found. The fact that OutputSet includes information on which patterns are frequent and where in the dataset the instances of such patterns are located, may be used or exploited by one or more entities, such as a compiler. The method500may then end at block518.

Having described the method500, additional detail is provided below regarding the sub-graph pattern mining technique that may be used.

Sub-graph pattern mining may be used to search for instances of a candidate pattern g in the DS. In order to improve performance, a mining of redundant candidate patterns in the dataset may be prevented. Before the mining starts, a verification or check may be performed to confirm that g has not been previously searched for and found in the dataset. If it has, then searching for g would be redundant.

Redundant candidate pattern detection decreases the number of candidate patterns that the method500needs to search. Redundant patterns may be generated because the growth of different sub-graph patterns may lead to one or more of their child patterns being isomorphic to each other.

In order to quickly detect if two sub-graphs are isomorphic to each other, a sub-graph pattern labeling system may be used. Every sub-graph pattern may be represented as a string of characters and the strings for the two sub-graphs may be compared. If the strings are the same, the sub-graphs may be deemed isomorphic.

In some embodiments, the string format used to represent a sub-graph of n edges may take the form of:

with each edge being represented as:

and each node v may be represented as:

When checking for sub-graph isomorphism using strings, a necessary condition for the isomorphism to be confirmed may be that there should be a direct correspondence between the identifier labels L(v) of every node v of the two sub-graphs being compared. This condition may require that labels be given in a consistent fashion. For example, if two sub-graphs are isomorphic, even if their nodes are created in different order, their correspondent nodes may have the same labels. For this to occur, the label of a sub-graph pattern node may be defined as the order in which the node is visited during a depth-first traversal of the sub-graph.

The mining procedure may use the described string representation of sub-graphs to detect redundant candidate patterns by using H, which may hold the string representations of all frequent sub-graphs identified up to that point in the mining process. Every candidate pattern, before being mined for, may have its string representation looked up in H. If an identical string already exists in H, the candidate pattern is redundant and may be discarded. Otherwise, the mining proceeds. In some embodiments, instead of storing in H only the string representations of frequent sub-graphs, all candidate sub-graphs ever generated and tested could be stored. Storing all such candidate sub-graphs ever generated and tested might be impractical when mining large datasets with many possible patterns because H might consume too much memory.

The mining procedure of a candidate sub-graph pattern g′ may be state-based and work separately on each EFG of the dataset. For each EFG G, an attempt may be made to find all existing maps, if any, between nodes and edges in g′ and nodes and edges in G. In other words, an attempt may be made to locate instances of g′ in G. In order to build such maps, pairs {v_g′, v_G} of candidate nodes coming from g′ and G, respectively, may be selected. The choice may be made by iterating over the node sets of both g′ and G and simply picking the first pair that has not been tested yet. A pair may be added to a map if it is feasible, which means it may follow two rules: 1) attributes of v_G should be exactly the same as or a superset of attributes in v_g′, and 2) edge structure between v_g′ and v_G should be maintained. This may imply checking all incoming and outgoing edges of both nodes and making sure the other nodes to which such edges connect obey the preceding first rule.

If the sub-graph being searched for is a 0-edge sub-graph, the procedure might only end when all nodes in DS have been visited. Otherwise, the procedure may end when it has checked (in a manner that will be described later on) all elements of the list Instances(g, G) for every G in DS, where g is the parent sub-graph of g′. As the nodes of DS or elements of Instances(g, G) are visited, goal states and/or dead-end states may be found.

A goal state may be defined as having all nodes in g′ mapped to a set of (potentially non-unique) nodes in G. A dead-end state may be a partial mapping between nodes in g′ and G, where no additional pair of nodes from g′ and G can be found in order to proceed with the mapping construction. Every time a goal state is reached, the support values S_w and S_f of g′ may be updated with the support values of the located instance, G may be added to DS(g′) and the located instance of g′ may be added to Instances(g′, G).

As described above, when g′ is a k-edge sub-graph, with k>0, the mining procedure might only end when all elements in the list Instances(g, G) have been visited. An advantage of keeping Instances(g, G) may be the knowledge that the instances of g′ are necessarily a subset of the instances of its parent sub-graph g. As a consequence, the instances of g can be used as partial maps for g′. It may also be known that g′ differs from g only by an extra edge or an extra edge and node. The extra edge, during the growth process of g, may be connected to a node in g (the pivot node). Therefore, for every element in Instance(g′, G), the node pivot_G that is the correspondent, in G, to the pivot node may be selected. A check may be performed to determine if the extra edge or extra edge and node from g′ have their correspondents among those edges and nodes that are connected to pivot_G. If the correspondence exists, an instance has been found.

The technique described above may provide for using the instances of a sub-graph pattern as starting points when mining for its child sub-graph patterns (instead of visiting every node in the dataset of EFGs). The technique may be referred to as sub-graph pattern registration.

FIG. 6is exemplary of the process of mining for sub-graph patterns in accordance with one or more embodiments. InFIG. 6, 0-edge sub-graph patterns that have a single attribute associated to them are identified. Each of the nodes602,604,606, and608has an attribute associated with it. For example, the node602has attribute ‘a’ associated with it. The node604has attribute ‘b’ associated with it. The node606has attribute ‘c’ associated with it. The node608has attribute ‘d’ associated with it. The attributes ‘a’, ‘b’, ‘c’, and ‘d’ may be elements or members of the InitialAttributeList.

As shown inFIG. 6, support values Sw, Sf, and Sm may be calculated for each of the nodes602-608. The node606is shown with a large/heavy ‘X’ through it to indicate that the node606is determined to not be frequent, as its support value of Sm=0.027 may be less than a minimum support value of MinSup=0.03 in this example. Conversely, the support values Sm for the nodes602,604, and608are greater than or equal to MinSup=0.03 in this example. As such, the nodes602,604, and608may be determined to be frequent.

FIG. 7depicts a resumption of the exemplary mining process for 0-edge sub-graph patterns relative toFIG. 6. Those patterns that are frequent inFIG. 6(e.g., patterns associated with nodes602,604, and608) may have their attribute sets of k attributes (where k=1 in this example) combined to form 0-edge sub-graph patterns with attribute sets of (k+1) attributes. Thus, patterns associated with attributes {a, b}, {a, d}, and {b, d} may be examined as candidate frequent sub-graph patterns as reflected by nodes702,704, and706, respectively. The new patterns may be mined for in the dataset, but none of them except the one with attribute set {b, d} (reflected by the node706) is frequent in this example. In this example, there is no way to proceed with the attribute set combination process, so the generation of 0-edge sub-graph patterns may complete.

One or more of the four frequent 0-edge sub-graph patterns (reflected by the nodes602,604,608, and706inFIG. 7) may be grown to generate 1-edge sub-graph patterns. For example,FIG. 8reflects the growth of the node602(which is circled inFIG. 7, and is given a node label of ‘0’ inFIG. 8). InFIG. 8, the spanned child patterns incorporating the node ‘0’ and candidate nodes labeled ‘1’ with attributes as shown are on the right-hand side of arrow802. The child pattern804that is crossed might not be found in the dataset by sub-graph pattern mining. The child patterns806,808, and810may be found in the dataset, and their support values may be as shown. The child patterns806,808, and810may be frequent, and inserted into Q to be extended after all 0-edge sub-graph patterns are themselves extended and have their children also inserted into Q.

The 1-edge sub-patterns806,808, and810may in turn be grown or extended. For example, the pattern806(which is circled inFIG. 8) may be removed from Q and extended to span multiple 2-edge sub-graphs as shown inFIG. 9. Patterns904,906, and908on the right-hand side of arrow902inFIG. 9may have as a pivot node the node with label0with respect to candidate nodes labeled ‘2’. Patterns910,912, and914may have as a pivot node the node with label1with respect to candidate nodes labeled ‘2’. The pattern906inFIG. 9may also appear when the pattern808ofFIG. 8is grown. The second time that the pattern906appears (e.g., when extending or growing the pattern808), it might not be extended because the redundancy may be detected.

Embodiments of the disclosure may be tied to particular machines. For example, in some embodiments a computing device may be configured to discover supported patterns in flow graphs that have weights on attributes, nodes, or edges. The computing device may be configured to identify potential performance bottlenecks in connection with, e.g., an execution of a program. In some embodiments, the computing device may be configured to determine a frequency associated with one or more nodes or edges.

In some embodiments various functions or acts may take place at a given location and/or in connection with the operation of one or more apparatuses or systems. In some embodiments, a portion of a given function or act may be performed at a first device or location, and the remainder of the function or act may be performed at one or more additional devices or locations.

In some embodiments, an apparatus or system may comprise at least one processor, and memory storing instructions that, when executed by the at least one processor, cause the apparatus or system to perform one or more methodological acts as described herein. In some embodiments, the memory may store data, such as one or more structures, metadata, lines, tags, blocks, strings, etc.

The diagrams depicted herein are illustrative. There may be many variations to the diagram or the steps (or operations) described therein without departing from the spirit of the disclosure. For instance, the steps may be performed in a differing order or steps may be added, deleted or modified. All of these variations are considered a part of the disclosure.

It will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow.

APPENDIX

Definitions

k-edge sub-graph: A sub-graph composed of k edges. A 0-edge sub-graph is simply a single node.

Size of a sub-graph pattern: The number of edges the sub-graph has.

DS: Dataset of EFGs to be mined.

DS(g): Set of EFGs where instances of a sub-graph pattern g have been found.

S_w(g): The minimum attribute weight of an instance of a sub-graph pattern g, summed up over all instances of g.

S_f(g): The minimum edge weight of an instance of a sub-graph pattern g, summed up over all instances of g.

S_m(g): The support value of a sub-graph pattern g, defined as the maximum between S_w(g) and S_f(g).

MinSup: Minimum support value to be compared against S_m(g) when it is calculated for a candidate pattern g.

Frequent sub-graph pattern: A sub-graph that has its support value S_m higher than MinSup.

Pattern-growth or pattern extension: The process of adding to a sub-graph pattern either a single edge connecting two existing nodes of the pattern, or an edge connecting an existing node of the pattern to a new node, in order to generate a new sub-graph pattern. The extended sub-graph pattern is the parent sub-graph, and the pattern generated from the growth process is the child sub-graph.

Parent sub-graph pattern: A sub-graph pattern that is extended to generate other sub-graph patterns.

Child sub-graph pattern: A sub-graph pattern that has been generated by the extension of another sub-graph pattern (its parent).

From-node: Considering a directed edge connecting two nodes, it is the node that has the edge directed from it.

To-node: Considering a directed edge connecting two nodes, it is the node that has the edge directed towards it.

Pivot node: The from-node of the edge connected to a parent sub-graph in order to generate its child sub-graph.

Target node: The to-node of the edge connected to a parent sub-graph in order to generate its child sub-graph. May be a node that already exists in the parent sub-graph, or a new node.

k-generation of patterns: The set of all candidate sub-graph patterns that have the same size k.

Instance of a sub-graph pattern g: Mapping between the nodes and edges of g and a set of nodes and edges of an EFG G of DS.

Instances(g, G): List of instances of a sub-graph pattern g that appear in EFG G of DS.

InitialAttributeList: List of distinct attributes that the method user is interested in, and that will be used to create the 0-generation of sub-graph patterns.

CurrentAttributeList: List of distinct attributes that appear in the sub-graph patterns of the k-generation of sub-graphs, and that will be used to create the (k+1)-generation of sub-graphs, with k>=0.

OutputSet: Set of frequent sub-graph patterns found by the presented method.

Q: A data structure, preferably a queue, that holds all frequent sub-graph patterns that must still be extended.

H: A data structure, preferably a hash-table, that holds the string representation of all frequent sub-graph patterns and is used to look up whether a pattern has already been mined for.

C: A set of child sub-graph patterns.

Execution Flow Graph: A graph formed by nodes and edges. Weights may be associated with each node and each edge, sets of attributes may be associated to each node, and a value may be associated with each attribute associated with a node.FIG. 2is exemplary of a node and an edge of an Execution Flow Graph showing all their forming elements.