Processing search queries using a data structure
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification