Processing Search Queries Using A Data Structure

• US 20130103678A1
• Filed: 12/30/2011
• Published: 04/25/2013
• Est. Priority Date: 10/24/2011
• Status: Active Grant

• Current Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Original Assignee: Luciano Garcia-Banuelos
• Inventors: Tretjakov, Konstantin, Armas-Cervantes, Abel, Vilo, Jaak, Dumas, Marlon G., Garca-Bauelos, Luciano
• Granted Patent: US 8,521,724 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• 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 generating a data structure stored in a computer memory for use in performing a search query in a network of interconnected nodes, wherein the method comprises selecting landmark nodes by the following steps and showing 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.

2. A method according to claim 1, comprising storing in the data structure in association with each landmark node vertex data for each vertex in the network.

3. A method according to claim 2, wherein the vertex data comprises a distance from each vertex to the landmark node.

4. A method according to claim 2 wherein the vertex data comprises a shortest path tree.

5. A method according to claim 4 wherein the shortest path tree is in the form of a set of parent links wherein each parent link identifies an adjacent vertex node in the shortest path between the vertex and the landmark node.

6. A data structure, recorded on an electronic storage medium, generated by the method of claim 1 when used in a computer implemented method of processing a search query.

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

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

and

executing at the computer device an application for generating a search result, the application performing the following steps;

accessing the data structure, in which each landmark 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 identifying the location of the source node and the target node in the shortest path trees to the landmark node;

for each 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 with the shortest distance; and

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

8. A method according to claim 7, wherein the measure of distance is generated by:

computing a first distance over the shortest path between the source node and the landmark node;

computing a second distance over the shortest path between the landmark node and the target node; and

summing the first and second distances.

9. A method according to claim 7, wherein generating the measure of distance includes:

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

10. A method according to claim 9, comprising:

summing 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. A method according to claim 9 wherein the measure of distance is generated by:

identifying in all pairs of nodes in a first paths 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 the edge of the shortest distance; and

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

12. A method according to claim 7 wherein the measure of distance is generated by:

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

executing a graph traversal from the source node, traversing only commonly recorded nodes, to update shortest path from the source node to the target node and

using the updated shortest path to determine the measure of distance.

13. A method according to claim 12 wherein the measure of distance is generated using the updated shortest path.

14. A method according to claim 7 wherein the step of providing a search result comprises displaying the search result to a user.

15. A method according to claim 7 wherein the step of providing a search result comprises providing the search result to a search function which generates a comparison between a plurality of search results to provide a set of outputs in ranked order.

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

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

18. A computer device for processing a search query to provide a search result, the computer device comprising:

a first component comprising a data structure, each 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 an application for generating a search result, the application performing the following steps;

accessing the data structure;

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

for each landmark 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 with the shortest distance; and

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

19. A computer program product comprising a non-transitory computer readable medium storing thereon computer readable instructions configured so as when executed on one or more processors to perform the operations of generating a data structure stored in a computer memory for use in performing a search query in a network of interconnected nodes including selecting landmark nodes by:

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.