Processing search queries in a network of interconnected nodes

• US 8,527,503 B2
• Filed: 12/30/2011
• Issued: 09/03/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, Garcia-Bauelos, Luciano, Armas-Cervantes, Abel, Vilo, Jaak, Dumas, Marlon G.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/341,373
• Publication Number:
  US 20130103671A1
• Time in Patent Office: 613 Days
• Field of Search: 707/716, 707/705, 370/217, 370/238, 701/201
• US Class Current: 707/716
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

A search query to provide a search result may be received, which identifies source and target nodes and an application for generating the search result. The application accesses a data structure holding landmark nodes, which store a shortest path tree in the form of a set of parent links. Each parent link can identify an adjacent vertex node in a shortest path between each node in the data structure and the landmark node. The location of the source node and the target node in the shortest path trees may be identified to the landmark node. For each landmark node, using the identified locations of the target node and source node, a measure of distance between the source node and the target may be generated. The landmark node with the shortest distance may be determined. A search result related to the shortest path tree of that landmark node may be provided.

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 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 a data structure holding a plurality of landmark nodes, each landmark 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;

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, wherein the measure of distance is generated by;

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 the paths between the source 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;

determining the landmark with the shortest distance; and

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

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

3. A method according to claim 1 wherein the 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.

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 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 a data structure holding a plurality of landmark nodes, each landmark 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;

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, 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;

determining the landmark with the shortest distance; and

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

7. A method according to claim 6 wherein the measure of distance is generated using updated shortest path trees.

8. A method according to claim 6 wherein the providing a search result comprises displaying the search result to a user.

9. A method according to claim 6 wherein the 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.

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

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

12. One or more computer-readable storage memories embodying computer readable instructions which, when executed, implement 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 a data structure holding a plurality of landmark nodes, each landmark 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;

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, wherein the measure of distance is generated by;

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 the paths between the source 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;

determining the landmark with the shortest distance; and

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

13. The one or more computer-readable storage memories according to claim 12 wherein the providing a search result comprises displaying the search result to a user.

14. The one or more computer-readable storage memories according to claim 12 wherein the 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.

15. The one or more computer-readable storage memories according to claim 12 wherein the search result comprises a list of node identifiers in the shortest path tree of the landmark with the shortest distance.

16. The one or more computer-readable storage memories according to claim 12 wherein the search result comprises the number of nodes in the shortest path tree of the landmark for the shortest distance.

17. A computing device comprising:

one or more processors;

one or more computer-readable storage memories embodying computer readable instructions which, when executed by the one or more processors, implement 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 a data structure holding a plurality of landmark nodes, each landmark 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;

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, wherein the measure of distance is generated by;

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 the paths between the source 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;

determining the landmark with the shortest distance; and

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

18. The computing device according to claim 17 wherein the providing a search result comprises displaying the search result to a user.

19. The computing device according to claim 17 wherein the 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.

20. The computing device according to claim 17 wherein the search result comprises a list of node identifiers in the shortest path tree of the landmark with the shortest distance.

21. The computing device according to claim 17 wherein the search result comprises the number of nodes in the shortest path tree of the landmark for the shortest distance.

22. One or more computer-readable storage memories embodying computer readable instructions which, when executed, implement 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 a data structure holding a plurality of landmark nodes, each landmark 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;

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, 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;

determining the landmark with the shortest distance; and

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

23. The one or more computer-readable storage memories according to claim 22 wherein the measure of distance is generated using updated shortest path trees.

24. The one or more computer-readable storage memories according to claim 22 wherein the providing a search result comprises displaying the search result to a user.

25. The one or more computer-readable storage memories according to claim 22 wherein the 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.

26. The one or more computer-readable storage memories according to claim 22 wherein the search result comprises a list of node identifiers in the shortest path tree of the landmark with the shortest distance.

27. The one or more computer-readable storage memories according to claim 22 wherein the search result comprises the number of nodes in the shortest path tree of the landmark for the shortest distance.

28. A computing device comprising:

one or more processors;

one or more computer-readable storage memories embodying computer readable instructions which, when executed by the one or more processors, implement 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 a data structure holding a plurality of landmark nodes, each landmark 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;

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, 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;

determining the landmark with the shortest distance; and

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

29. The computing device according to claim 28 wherein the measure of distance is generated using updated shortest path trees.

30. The computing device according to claim 28 wherein the providing a search result comprises displaying the search result to a user.

31. The computing device according to claim 28 wherein the 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.

32. The computing device according to claim 28 wherein the search result comprises a list of node identifiers in the shortest path tree of the landmark with the shortest distance.

33. The computing device according to claim 28 wherein the search result comprises the number of nodes in the shortest path tree of the landmark for the shortest distance.