Processing Search Queries In A Network Of Interconnected Nodes
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; 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;
determining the landmark with the shortest distance; and
providing a search result related to the shortest path tree of that landmark.
1 Assignment
0 Petitions
Accused Products
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.
7 Citations
12 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; determining the landmark with the shortest distance; and providing a search result related to the shortest path tree of that landmark. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computer device for processing a search query to provide a search result, the computer device comprising:
-
a first component in the form of a data structure holding a plurality of landmark nodes, 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.
-
-
12. A computer program product comprising a non-transitory computer readable medium storing thereon computer readable instructions so as when executed on one or more processors to perform the operations of:
-
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; determining the landmark with the shortest distance; and providing a search result related to the shortest path tree of that landmark.
-
Specification