Processing search queries using a data structure

• US 9,524,316 B2
• Filed: 04/18/2014
• Issued: 12/20/2016
• Est. Priority Date: 11/15/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Floreskul, Volodymyr, Tretjakov, Konstantin, Dumas, Marlon Gerardo, Saabas, Ando
• Primary Examiner(s): Nguyen, Phong
• Application Number:
  US14/256,574
• Publication Number:
  US 20150142796A1
• Time in Patent Office: 977 Days
• Field of Search: 707/736, 707/797, 707/E17.012
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

The disclosure relates to of generating a data structure stored in a computer memory for use in performing a search query to determine a separation between nodes in a network of interconnected nodes, wherein the method comprises: selecting a set of landmark nodes from the network; and for at least two of the landmark nodes in the set; generating a path tree for each landmark node that indicates a separation between the landmark node and each of a plurality of nodes; wherein the generating is configured to limit the number of path trees each of said plurality of nodes may appear in to no more than a predetermined number of path trees. A method of processing a data structure is also disclosed.

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 in a network of interconnected nodes, at least one of the interconnected nodes being a landmark node; and

executing at the computer device an application for generating a search result, the application performing operations of;

accessing a data structure from a memory of the computer device in which the landmark node has stored therewith a path tree that indicates a separation between the landmark node and each of a plurality of nodes, each of said plurality of nodes being limited to appearing in no more than a predetermined number of path trees;

identifying the landmark node in the accessed data structure having at least one of the source node and the target node in their path tree; and

determining a search result related to the path tree of the identified landmark node.

2. A method according to claim 1, wherein the data structure has stored, for each landmark node, an indication of a separation to at least one other landmark node.

3. A method according to claim 1, wherein the data structure has stored, for each landmark node, an indication of a separation to every other landmark node.

4. A method according to claim 1, wherein the determining the search result is related to two of said landmark nodes and uses an indication of a separation between said two landmark nodes.

5. A method according to claim 1, wherein the application further performs:

detecting whether any nodes appear at least twice in the search result; and

, if so detected, modifying the search result such that each node only appears once in the search result.

6. A method according to claim 1, wherein the application further performs:

modifying the search result to take account of connections between nodes that are present in the interconnected network but that are not present in any of the path trees.

7. A method according to claim 1, wherein at least one of the interconnected nodes is a witness node and the application further performs:

identifying a stored witness node in the data structure;

using the stored witness node to determine separations between the witness node and at least two identified landmark nodes; and

providing a search result related to the separation between said witness node and the at least two identified landmark nodes.

8. A method according to claim 1, wherein the path trees each of said plurality of nodes may appear in is limited to those path trees of the closest landmark nodes to said node.

9. A method according to claim 1, wherein the separation indication comprises both distances and paths between the landmark node and nodes in the path trees.

10. A method according to claim 1, wherein the separation indication is presented on a display of the computing device.

11. A computer device for processing a search query to determine a separation between a source node and a target node to provide a search result in a network of interconnected nodes comprising a landmark node, the computer device comprising:

a first component comprising a data structure in which the landmark node has stored therewith a shortest path tree that indicates a separation between the landmark node and each of a plurality of nodes, each of said plurality of nodes appearing in no more than a predetermined number of shortest path trees such that the plurality of nodes are limited to a number of shortest path trees in which it can be included; and

a second component comprising a processor configured to execute an application for generating a search result using instructions stored on the computer device, the application performing the following steps responsive to execution by the processor;

accessing the data structure;

identifying the landmark node in the accessed data structure having at least one of the source node and the target node in their shortest path trees; and

determining a search result related to the shortest path tree of the identified landmark node.

12. A computing device as recited in claim 11, wherein the data structure has stored, for each landmark node, an indication of a separation to at least one other landmark node.

13. A system comprising:

a processor; and

one or more computer-readable storage media storing instructions that, responsive to execution by the processor, cause the system to perform operations comprising;

receiving a search query in the form of a digital message, the query identifying a source node and a target node in a network of interconnected nodes, at least one of the interconnected nodes being a landmark node;

accessing a data structure in which the landmark node has stored therewith a path tree that indicates a separation between the landmark node and each of a plurality of nodes, each of said plurality of nodes being limited to appearing in no more than a predetermined number of path trees;

identifying the landmark node in the accessed data structure having at least one of the source node and the target node in their path tree; and

determining a search result related to the path tree of the identified landmark node.

14. A system as recited in claim 13, wherein the data structure has stored, for each landmark node, an indication of a separation to at least one other landmark node.

15. A system as recited in claim 13, wherein the determining the search result is related to two landmark nodes and uses an indication of a separation between said two landmark nodes.

16. A system as recited in claim 13, the operations further comprising detecting whether any nodes appear at least twice in the search result;

and, if so detected, modifying the search result such that each node only appears once in the search result.

17. A system as recited in claim 13, the operations further comprising modifying the search result to take account of connections between nodes that are present in the interconnected network but that are not present in any of the path trees.

18. A system as recited in claim 13, wherein at least one of the interconnected nodes is a witness node and the operations further comprising:

identifying a stored witness node in the data structure;

using the stored witness node to determine separations between the witness node and at least two identified landmark nodes; and

providing a search result related to the separation between said witness node and the at least two identified landmark nodes.

19. A system as recited in claim 13, wherein the path trees each of said plurality of nodes may appear in is limited to those path trees of the closest landmark nodes to said node.

20. A system as recited in claim 13, wherein the separation indication comprises both distances and paths between the landmark node and nodes in the path trees.