Parallel Top-K Simple Shortest Paths Discovery
AssigneeInternational Business Machines Corporation
InventorsYuan-Chi Chang, Mustafa Canim
Life of this patent
Estimating the term…
Abstract
A method for searching the top-K simple shortest paths between a specified source node and a specified target node in a graph, with graph data partitioned and distributed across a plurality of computing servers, the method including a parallel path search initialized from either one or both of the source and target nodes and traversing the graph by building likely path sequences for a match. Each computing server determines and forwards a path sequence as discovery progresses until the top-K paths are discovered.
Claims32
A method for determining a portion of a path in a distributed network of nodes between a source node and a target node, wherein graph data representing a portion of a topology of the distributed network of nodes is stored by a computing server, the method comprising:
- receiving a batch of incomplete path sequences between the source node and the target node;
- receiving a current cutoff threshold;
- updating the current cutoff threshold upon determining that a local cutoff threshold of the computing server is less than the current cutoff threshold, wherein the current cutoff threshold is updated to take a value of the local cutoff threshold;
- removing each of the incomplete path sequences containing a loop from the batch of incomplete path sequences to determine an updated batch;
- appending a looked up edge to the updated batch upon determining that a total path weight of the updated batch is less than the current cutoff threshold to determine an appended batch;
- and
- outputting the updated batch to at least one additional computing server storing graph data representing an additional portion of the topology of the distributed network of nodes.
A method for determining a path in a distributed network of nodes, wherein graph data representing a topology of the distributed network of nodes is partitioned and stored among a plurality of computing servers connected via communication switches, the method comprising:
- initializing a search, in response to a query at a source node, at an initial computing server storing a portion of the graph data corresponding to the source node;
- determining, by the plurality of computing servers, a plurality of path sequences forming the path between the source node and a target node, each of the plurality of computing servers, excluding a terminating computing server,
- determining at least one path sequence between at least two immediate neighboring nodes along the path;
- and
- sending the at least one path sequence to at least one additional computing server of the plurality of computing servers storing a respective portion of the graph data between the source node toward the target node upon determining that a path weight of the at least one path sequence is smaller than a cutoff threshold;
- and
- determining, by the terminating computing server, at least one path sequence directly to the target node given the at least one path sequence of at least one previous computing server.
A method for determining a top-K simple shortest path in a distributed network of nodes, wherein graph data representing a topology of the distributed network of nodes is partitioned and stored among a plurality of computing servers connected via communication switches, the method comprising:
- receiving a query at a source node;
- initializing a search in response to the query at an initial computing server storing a portion of the graph data corresponding to the source node;
- determining at least one path sequence directly from the source node to its direct, immediate neighboring nodes;
- and
- sending the at least one path sequence to at least one additional computing server storing a respective portion of the graph data between the source node toward a target node upon determining that a path weight of the at least one path sequence is smaller than a cutoff threshold;
- for each additional computing server, in parallel,
- receiving a batch of incomplete path sequences including the at least one path sequence and a current cutoff threshold;
- updating the current cutoff threshold upon determining that a local cutoff threshold of the at least one additional computing server is less than the current cutoff threshold, wherein the current cutoff threshold is updated to take a value of the local cutoff threshold;
- removing each of the incomplete path sequences containing a loop from the batch of incomplete path sequences to determine an updated batch;
- appending a looked up edge to the updated batch upon determining that a total path weight of the updated batch is less than the current cutoff threshold to determine an appended batch;
- updating a top-K list of path sequences upon determining that the path sequences of the appended batch reaches the target node;
- and
- exiting upon determining that none of the additional computing servers have more sequences to exchange and merge into the top-K list of path sequences and outputting the top-K list of path sequences.
A computer program product for determining a portion of a path in a distributed network of nodes between a source node and a target node, wherein graph data representing a portion of a topology of the distributed network of nodes is stored by the computer program product, the computer program product comprising:
- a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
- computer readable program code configured to receive a batch of incomplete path sequences between the source node and the target node and a current cutoff threshold;
- computer readable program code configured to update the current cutoff threshold upon determining that a local cutoff threshold of the computer program product is less than the current cutoff threshold, wherein the current cutoff threshold is updated to take a value of the local cutoff threshold;
- computer readable program code configured to remove each of the incomplete path sequences containing a loop from the batch of incomplete path sequences to determine an updated batch;
- computer readable program code configured to append a looked up edge to the updated batch upon determining that a total path weight of the updated batch is less than the current cutoff threshold to determine an appended batch;
- and
- computer readable program code configured to output the updated batch to at least one additional computer program product storing graph data representing an additional portion of the topology of the distributed network of nodes.
A computer program product for determining a path in a distributed network of nodes, wherein graph data representing a topology of the distributed network of nodes is partitioned and stored among a plurality of computing servers connected via communication switches, the computer program product comprising:
- a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
- computer readable program code configured to initialize a search, in response to a query at a source node, at an initial computing server storing a portion of the graph data corresponding to the source node;
- computer readable program code configured to determine, by the plurality of computing servers, a plurality of path sequences forming the path between the source node and a target node, each of the plurality of computing servers, excluding a terminating computing server,
- determining at least one path sequence between at least two immediate neighboring nodes along the path;
- and
- sending the at least one path sequence to at least one additional computing server of the plurality of computing servers storing a respective portion of the graph data between the source node toward the target node upon determining that a path weight of the at least one path sequence is smaller than a cutoff threshold;
- and
- computer readable program code configured to determine, by the terminating computing server, at least one path sequence directly to the target node given the at least one path sequence of at least one previous computing server.
A computer program product for determining a top-K simple shortest path in a distributed network of nodes, wherein graph data representing a topology of the distributed network of nodes is partitioned and stored among a plurality of computing servers connected via communication switches, the computer program product comprising:
- a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
- computer readable program code configured to receive a query at a source node;
- computer readable program code configured to initialize a search in response to the query at an initial computing server storing a portion of the graph data corresponding to the source node;
- computer readable program code configured to determine at least one path sequence directly from the source node to its direct, immediate neighboring nodes;
- and
- computer readable program code configured to send the at least one path sequence to at least one additional computing server storing a respective portion of the graph data between the source node toward a target node upon determining that a path weight of the at least one path sequence is smaller than a cutoff threshold;
- for each additional computing server, in parallel,
- receiving a batch of incomplete path sequences including the at least one path sequence and a current cutoff threshold;
- updating the current cutoff threshold upon determining that a local cutoff threshold of the at least one additional computing server is less than the current cutoff threshold, wherein the current cutoff threshold is updated to take a value of the local cutoff threshold;
- removing each of the incomplete path sequences containing a loop from the batch of incomplete path sequences to determine an updated batch;
- appending a looked up edge to the updated batch upon determining that a total path weight of the updated batch is less than the current cutoff threshold to determine an appended batch;
- updating a top-K list of path sequences upon determining that the path sequences of the appended batch reaches the target node;
- and
- exiting upon determining that none of the additional computing servers have more sequences to exchange and merge into the top-K list of path sequences and outputting the top-K list of path sequences.
Dependencies are inferred from the claim text.