Using activation paths to cluster proximity query results

• US 20080183695A1
• Filed: 03/27/2007
• Published: 07/31/2008
• Est. Priority Date: 01/31/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Jadhav, Apurva Rameshchandra
• Granted Patent: US 7,636,713 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A search engine finds and ranks information in clusters so a user can select information listed in search results that are closer to his information needs. To do so, the search engine receives a proximity query and executes it against an entity-relationship graph. The search engine finds those entities in the graph that have similar relationships between nodes. For example, two entities in a graph may be connected to entirely different nodes, but they may connect to those different nodes using similarly labeled paths. The search engine identifies the relationship between the nodes, clusters entities that are connected by similar relationships, and presents the clustered information to the user as part of the search results. In this way, the search engine provides a user with a results from which the user can select the group of results that most closely match his information need.

Claims

1. A method for displaying search results to a user comprising:

receiving, by a search engine, user input to perform a proximity query on a graph, wherein said graph includes one or more nodes and one or more edges;

executing, by the search engine, the proximity query, wherein said proximity query traverses the one or more nodes and one or more edges of the graph to generate a set of result nodes, a set of activator nodes, and at least one activation value for at least a portion of the one or more nodes in the graph;

generating, by the search engine, a set of result clusters that include one or more result nodes from said set of result nodes, wherein said one or more result nodes are related by a common path type to at least one activator node in said set of activator nodes;

ranking, by the search engine, said one or more result nodes in said result clusters based on the activation value of each of the one or more result nodes in said result clusters; and

displaying to a user a representation of said result clusters.

2. The method of claim 1, wherein executing the proximity query comprises:

identifying said set of activator nodes by determining which of said one or more nodes in the graph satisfy a predicate clause in the proximity query;

identifying said set of result nodes by determining which of said one or more nodes are of a type specified in the proximity query;

assigning an initial activation value to each of the activator nodes in said set of activator nodes;

iterating over each of the activator nodes, calculating a neighbor activation value for a set of neighbor nodes of said activator node, wherein said neighbor activation value is based at least in part on the initial activation value of the activator node;

computing a total accrued activation value for each of said result nodes in the set of result nodes;

wherein the total accrued activation value for each of said result nodes in the set of result nodes is computed by iteratively adding the neighbor activation values for each of said neighbor nodes; and

ranking the set of result nodes based on the total accrued activation value.

3. The method of claim 1, wherein generating the result clusters includes:

computing a path set activation value between at least one activator node in said set of activator nodes and at least one result node in said set of result nodes; and

for each path set activation value above a certain threshold;

creating a result cluster; and

inserting the at least one result node in said result cluster.

4. The method of claim 3, further comprising labeling the result cluster by the common path type.

5. The method of claim 3, wherein computing the activation path sets includes performing a breadth first algorithm.

6. The method of claim 5, wherein the breadth first algorithm is limited to a fixed number of levels of exploration.

7. The method of claim 3, wherein the threshold is the top ten contributing neighbors

8. The method of claim 3, wherein the threshold includes the neighbors that account for a majority of the path set activation value.

9. The method of claim 1, wherein ranking, by the search engine, said one or more result nodes in said result clusters includes:

determining a score for each result node in a result cluster, wherein said score based on said path set activation value; and

sorting the result nodes based on said scores.

10. The method of claim 1, wherein said result clusters are adjusted based on node prestige.

11. A machine-readable medium for displaying search results to a user, the machine-readable medium carrying instructions which, when processed by one or more processors, causes the one or more processors to perform the method of:

comprising;

receiving, by a search engine, user input to perform a proximity query on a graph, wherein said graph includes one or more nodes and one or more edges;

executing, by the search engine, the proximity query, wherein said proximity query traverses the one or more nodes and one or more edges of the graph to generate a set of result nodes, a set of activator nodes, and at least one activation value for at least a portion of the one or more nodes in the graph;

generating, by the search engine, a set of result clusters that include one or more result nodes from said set of result nodes, wherein said one or more result nodes are related by a common path type to at least one activator node in said set of activator nodes;

ranking, by the search engine, said one or more result nodes in said result clusters based on the activation value of each of the one or more result nodes in said result clusters; and

displaying to a user a representation of said result clusters.

12. The machine-readable medium of claim 11, wherein executing the proximity query comprises:

identifying said set of activator nodes by determining which of said one or more nodes in the graph satisfy a predicate clause in the proximity query;

identifying said set of result nodes by determining which of said one or more nodes are of a type specified in the proximity query;

assigning an initial activation value to each of the activator nodes in said set of activator nodes;

iterating over each of the activator nodes, calculating a neighbor activation value for a set of neighbor nodes of said activator node, wherein said neighbor activation value is based at least in part on the initial activation value of the activator node;

computing a total accrued activation value for each of said result nodes in the set of result nodes;

wherein the total accrued activation value for each of said result nodes in the set of result nodes is computed by iteratively adding the neighbor activation values for each of said neighbor nodes; and

ranking the set of result nodes based on the total accrued activation value.

13. The machine-readable medium of claim 11, wherein generating the result clusters includes:

computing a path set activation value between at least one activator node in said set of activator nodes and at least one result node in said set of result nodes; and

for each path set activation value above a certain threshold;

creating a result cluster; and

inserting the at least one result node in said result cluster.

14. The machine-readable medium of claim 13, further comprising labeling the result cluster by the common path type.

15. The machine-readable medium of claim 13, wherein computing the activation path sets includes performing a breadth first algorithm.

16. The machine-readable medium of claim 15, wherein the breadth first algorithm is limited to a fixed number of levels of exploration.

17. The machine-readable medium of claim 13, wherein the threshold is the top ten contributing neighbors

18. The machine-readable medium of claim 13, wherein the threshold includes the neighbors that account for a majority of the path set activation value.

19. The machine-readable medium of claim 11, wherein ranking, by the search engine, said one or more result nodes in said result clusters includes:

determining a score for each result node in a result cluster, wherein said score based on said path set activation value; and

sorting the result nodes based on said scores.

20. The machine-readable medium of claim 11, wherein said result clusters are adjusted based on node prestige.