PROCESSING SEARCH QUERIES USING A DATA STRUCTURE

• US 20150142796A1
• Filed: 04/18/2014
• Published: 05/21/2015
• Est. Priority Date: 11/15/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Saabas, Ando, Floreskul, Volodymyr, Tretjakov, Konstantin, Dumas, Marlon Gerardo
• Granted Patent: US 9,524,316 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• 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 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.

2. A method according to claim 1, further comprising storing for each landmark node, an indication of a separation to at least one other landmark node.

3. A method according to claim 1, further comprising storing, for each landmark node, an indication of a separation to every other landmark node.

4. A method according to claim 1, further comprising:

selecting at least one witness node from the network for determining a separation between at least two landmark nodes; and

storing said witness node.

5. A method according to claim 1, wherein limiting the number of path trees each of said plurality of nodes may appear in comprises limiting each of said plurality of nodes to appear in the path trees of only the closest landmark nodes to said node.

6. A method according to claim 1, further comprising:

storing information relating to connections between nodes that are present in the interconnected network but that are not present in any of the generated path trees.

7. A method according to claim 1, wherein each path tree is a shortest path tree in the form of a set of links, each link identifying an adjacent node in the network.

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

9. A method according to claim 1, wherein the indication of a separation comprises only distances between landmark nodes and nodes in the path trees.

10. 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 in which each 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 appearing in no more than a predetermined number of path trees;

identifying landmark nodes 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 at least one of those landmark nodes.

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

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

13. A method according to claim 10, 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.

14. A method according to claim 10, 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.

15. A method according to claim 10, 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.

16. A method according to claim 10, 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 said at least two of the identified landmark nodes; and

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

17. A method according to claim 10, 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.

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

19. A method according to claim 10, wherein the separation indication is presented to a user.

20. 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 at least one landmark node, the computer device comprising:

a first component comprising a data structure in which each 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,

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;

identifying landmark nodes 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 at least one of those landmark nodes.