Processing search queries using a data structure

• US 8,521,724 B2
• Filed: 12/30/2011
• Issued: 08/27/2013
• Est. Priority Date: 10/24/2011
• Status: Active Grant

• Current Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Original Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Inventors: Tretjakov, Konstantin, Garca-Bauelos, Luciano, Armas-Cervantes, Abel, Vilo, Jaak, Dumas, Marlon G.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/341,488
• Publication Number:
  US 20130103678A1
• Time in Patent Office: 606 Days
• Field of Search: 707/716, 707/722, 707/723, 370/217, 370/238, 370/338, 701/201
• US Class Current: 707/716
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

According to an embodiment, there is provided a method of generating a data structure stored in computer memory for processing a search query in a network of interconnected nodes, wherein the method comprises selecting landmark nodes by the following steps and storing the selected landmark nodes in the data structure: sampling from the network nodes a first sample of vertex pairs, computing the shortest path for each vertex pair, each shortest path comprising a set of vertices between each vertex in the vertex pair; identifying a first landmark node which occurs in more of the shortest paths more often than any other vertex; removing from the network vertices shortest paths including the first landmark node and identifying a second landmark node which occurs in more of the remaining shortest paths than any other remaining vertex.

Claims

1. A method of processing a search query to provide a search result, the method comprising

receiving at a computer device a search query message, the search query message identifying a source node and a target node;

responsive to receiving the search query message, accessing a data structure, wherein each landmark node identified within the data structure has stored therewith a shortest path tree in the form of a set of parent links, wherein each parent link identifies an adjacent vertex node;

for each landmark node, identifying a location of the source node and a location of the target node in the shortest path trees to the landmark node;

for each landmark node, generating a measure of distance between the source node and the target node based, at least in part, on said identified locations;

determining the landmark node with the shortest distance; and

providing a search result related to the shortest path tree of that landmark node,

wherein generating a measure of distance comprises;

identifying a common ancestor node in the shortest path trees from the source node and the target node to the landmark node;

identifying all pairs of nodes in a first path between the source node and the common ancestor node and a second path between the common ancestor node and the target node;

locating any of said pairs which are edges;

identifying an edge of the shortest distance; and

using the identified edge to determine the measure of distance between the source node and the target node.

2. A method according to claim 1, wherein providing a search result comprises displaying the search result to a user.

3. A method according to claim 1 wherein providing a search result comprises providing the search result to a search function configured to generate a comparison between a plurality of search results to provide a set of outputs in ranked order.

4. A method according to claim 1 wherein the search result comprises a list of node identifiers in the shortest path tree of the landmark with the shortest distance.

5. A method according to claim 1 wherein the search result comprises the number of nodes in the shortest path tree of the landmark for the shortest distance.

6. A computer device comprising:

a first component comprising a data structure including information associated with at least one landmark node, each landmark node of the at least one landmark node having stored therewith a shortest path tree in the form of a set of parent links wherein each parent link identifies an adjacent vertex node in the shortest path between each node in the data structure and the landmark node; and

a second component comprising a processor configured to execute a method for generating a search result, the method comprising;

accessing the data structure effective to identify each landmark node of the at least one landmark node;

for each identified landmark node, identifying the location of the source node and the target node in the shortest path trees to the landmark node;

for each identified landmark node, using the identified locations of the target node and source node to generate a measure of distance between the source node and the target node;

determining the landmark node of the at least one landmark node with the shortest distance; and

providing a search result related to the shortest path tree of said determined landmark,

wherein to generate a measure of distance, the second component is further configured to;

identify a common ancestor node in the shortest path trees from the source node and the target node to the landmark node;

identify all pairs of nodes in a first path between the source node and the common ancestor node and a second path between the common ancestor node and the target node;

locate any of said pairs which are edges;

identify an edge of the shortest distance; and

use the identified edge to determine the measure of distance between the source node and the target node.

7. One or more computer-readable storage memory embodying processor-executable instructions which, responsive to execution by at least one processor, are configured to:

receive a search query identifying a source node and a target node;

responsive to receiving the search query, access a data structure effective to identify at least one landmark node within the data structure, wherein each landmark node identified within the data structure has stored therewith a shortest path tree in the form of a set of parent links, wherein each parent link identifies an adjacent vertex node;

identify, for each identified landmark node within the data structure, a location of the source node and the target node in the shortest path trees to said identified landmark node;

generate, for each identified landmark node within the data structure, a measure of distance between the source node and the target node based, at least in part, on said identified locations of the target node and source node;

determine, using each generated measure of distance, a landmark node with a shortest measure of distance; and

provide a search result based, at least in part, on the shortest path tree of said determined landmark node with the shortest measure of distance,

wherein the processor-executable instructions to generate a measure of distance are further configured to;

identify a common ancestor node in the shortest path trees from the source node and the target node to the landmark node;

identify all pairs of nodes in a first path between the source node and the common ancestor node and a second path between the common ancestor node and the target node;

locate any of said pairs which are edges;

identify an edge of the shortest distance; and

use the identified edge to determine the measure of distance between the source node and the target node.

8. The one or more computer-readable storage memory of claim 7, wherein the processor-executable instructions to generate, for each identified landmark node, a measure of distance, are further configured to:

compute a first distance using a shortest path between the source node and said identified landmark node;

compute a second distance using a shortest path between said identified landmark node and the target node; and

sum the first and second distances.

9. The one or more computer-readable storage memory of claim 7, wherein the processor-executable instructions to generate the measure of distance are further configured to:

identify a common ancestor node in the shortest path trees from the source node and the target node to the landmark node.

10. The one or more computer-readable storage memory of claim 9, the processor-executable instructions further configured to:

sum a first distance from the source node to the common ancestor node and a second distance from the common ancestor node to the target nodes to generate the measure of distance.

11. The one or more computer-readable storage memory of claim 7, wherein the processor-executable instructions to generate the measure of distance are further configured to:

record, for each identified landmark node, nodes in common between the shortest path trees from the source node and the target node to the identified landmark node;

execute, traversing only the commonly recorded nodes, a graph traversal from the source node to update a shortest path from the source node to the target node and use the updated shortest path to determine the measure of distance.

12. The one or more computer-readable storage memory of claim 7, wherein the processor-executable instructions to provide a search result are further configured to:

provide the search result to a search function, the search function configured to generate a comparison between a plurality of search results to provide a set of outputs in ranked order.