US 8,527,503 B2Granted

Processing search queries in a network of interconnected nodes

AssigneeSkype

InventorsKonstantin Tretjakov, Luciano Garcia-Bañuelos, Abel Armas-Cervantes, Jaak Vilo, Marlon G. Dumas

Life of this patent

Estimating the term…

Loading patent…

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.

Claims33

Dependent claims

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.

12 more elements

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.

12 more elements

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.

14 more elements

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.

10 more elements

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.

12 more elements

Dependencies are inferred from the claim text.