Parallel Top-K Simple Shortest Paths Discovery

摘要

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.

主权项

1. 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.