DISCOVERING AND EXPLOITING RELATIONSHIPS IN SOFTWARE REPOSITORIES

• US 20100211924A1
• Filed: 02/28/2010
• Published: 08/19/2010
• Est. Priority Date: 07/05/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zimmermann, Thomas, Khoo, Yit Phang, Begel, Andrew, Venolia, Gina D.
• Granted Patent: US 9,129,038 B2
• Time in Patent Office: Days
• US Class Current: 717/101
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 8/74 Reverse engineering; Extracting design information from source code

Abstract

Software development items can be represented in a graph data structure. Relationships between the represented items can be detected and reflected in the graph data structure. Queries can be run against the data structure to determine which software development items are related to each other. Implicit query can be implemented in a software development context. A graph browser can present panes showing related items.

In some embodiments, a set of regular expressions can be used to identify paths in a graph. Probability scores for the identified paths can be computed. Path data for the identified paths, including the probability scores, can be stored in a searchable location accessible by one or more applications. A query of the path data can be processed to return query results associated with at least one of the identified paths.

Claims

1. One or more computer-readable storage media having instructions stored thereon that, when executed, perform acts comprising:

identifying paths in a graph, wherein one or more of the identified paths are defined by a set of regular expressions, and wherein nodes of the graph represent software development items and are separated by edges describing relationships between nodes;

computing probability scores for the identified paths; and

storing path data for the identified paths in a searchable location accessible by one or more applications, wherein the path data includes the computed probability scores.

2. The one or more computer-readable storage media of claim 1, further comprising processing a query of the path data to return query results associated with at least one of the identified paths, wherein the query results satisfy one or more terms of the query.

3. The one or more computer-readable storage media of claim 2, wherein the at least one identified path comprises two nodes separated by an intervening node and intervening edges.

4. The one or more computer-readable storage media of claim 3, wherein one or both of the intervening node or intervening edges describe a connection between the two nodes in the at least one identified path.

5. The one or more computer-readable storage media of claim 1, wherein computing the probability scores comprises computing at least one individual probability score based on a linguistic similarity between two individual paired nodes of the graph.

6. The one or more computer-readable storage media of claim 5, wherein computing the probability scores comprises:

determining an extent of linguistic similarity between the two individual paired nodes; and

based on the extent of linguistic similarity, computing the at least one individual probability score.

7. The one or more computer-readable storage media of claim 1, further comprising processing a query of the path data to return query results associated with a plurality of the identified paths, and further comprising ranking the individual paths of the plurality of identified paths based at least in part on one or more of the computed probability scores.

8. The one or more computer-readable storage media of claim 1, further comprising loading less than an entirety of the graph in memory prior to identifying the paths of the graph and computing the probability scores.

9. The one or more computer-readable storage media of claim 1, further comprising pruning a portion of the nodes of the graph prior to identifying the paths of the graph.

10. A platform comprising:

a graph builder configured to represent software development items as nodes of a graph and to detect relationships between individual nodes of the graph;

a graph analysis module configured to utilize a set of one or more user-defined regular expressions to compute path data for paths of the graph, wherein one or more of the paths are defined by an individual user-defined regular expression, and wherein individual paths comprise two or more of the nodes and at least one edge describing at least one of the relationships; and

a query module configured to;

receive a query; and

responsive to receiving the query, search the path data and return query results describing at least one of the paths.

11. The platform of claim 10, wherein the graph analysis module is further configured to:

load a portion of the graph into memory prior to computing the path data;

or

prune one or more nodes of the graph prior to computing the path data.

12. The platform of claim 10, wherein the graph analysis module is further configured to compute probability scores for the paths, and wherein at least one of the probability scores is computed based on linguistic similarity between individual nodes of one or more of the paths.

13. The platform of claim 12, wherein the least one path described in the query results comprises a plurality of individual described paths, and wherein the query module is further configured to rank the individual described paths based at least in part on one or more of the probability scores.

14. The platform of claim 10, wherein the least one path described in the query results includes two paired nodes separated by an intervening node and intervening edges, and wherein one or both of the intervening node or intervening edges describe a connection between the two paired nodes.

15. One or more computer-readable storage media having instructions stored thereon that, when executed, perform acts comprising:

providing path data for a graph based on a set of regular expressions, wherein providing the path data comprises;

identifying paths of the graph, wherein at least one of the identified paths is defined by an individual regular expression of the set, and wherein the identified paths include nodes representing software development items and edges describing relationships between individual nodes;

computing probability scores for individual identified paths;

identifying additional paths, wherein individual identified additional paths comprise two or more of the identified paths; and

computing additional probability scores for the identified additional paths based on the computed probability scores; and

processing a query of the path data to return query results that satisfy the query, wherein processing the query comprises ranking multiple nodes to be returned in the query results based at least in part on one or more of the computed probability scores or computed additional probability scores.

16. The one or more computer-readable storage media of claim 15, wherein computing the probability scores for the individual identified paths comprises assigning a standard probability score to the at least one of the individual identified paths.

17. The one or more computer-readable storage media of claim 15, wherein computing the probability scores for the individual identified paths comprises computing individual probability scores for each of one or more of the individual identified paths based on linguistic similarities between individual paired nodes of the one or more individual identified paths.

18. The one or more computer-readable storage media of claim 17, wherein computing the individual probability scores comprises:

determining an extent of textual overlap between the individual paired nodes; and

based on the extent of textual overlap, computing the individual probability scores.

19. The one or more computer-readable storage media of claim 15, further comprising restricting access to one or more of the nodes based on a user profile.

20. The one or more computer-readable storage media of claim 15, wherein the software development items include a person.