Paper Notes: PeeK  Pruning for Kth Shortest Paths
Last updated on October 15, 2024 am
Paper Notes: PeeK  Pruning for Kth Shortest Paths
Wang Feng, Shiyang Chen, Hang Liu, and Yuede Ji. PeeK: A PruneCentric Approach for K Shortest Path Computation. International Conference for High Performance Computing, Networking, Storage, and Analysis, 2023. https://doi.org/10.1145/3581784.3607110
Observation
The solution of KSP (K Shortest Paths) problem is typically a small sub set of all available paths, even though the K is very large in a very large graph.
K Upper Bound Pruning
Based on the observation, the authors propose a prunecentric approach to KSP computation. The key idea is to prune the search space.
SSSP: Single Source Shortest Path
Start from the source node, get the shortest path to each node in the graph. Its result can basically represented as a tree, with the source node as the root. See figure (b).
Reverse SSSP:
Start from the target node, get the shortest path from each node in the directed graph. Its result can basically represented as a tree, with the target node as the root, but in opposite direction. See figure (c).
By combining the SSSP tree and the reverse SSSP tree, we can get all possible paths from the source to the target. It can be divided into two cases:
 The vertices is not reachable from the source or to the target. For example, the vertex
a
can reach to the targett
viaa > s > f > j > t
, but is not reachable from the sources
. The distance sum is basically denoted as infinity.
 This is common for a sparse directed graph, as the observation above.
 The vertices is reachable from the source and to the target. For example, the vertex
o
can reach to the targett
viao > r > l > t
, and is reachable from the sources
bys > g > l > o
.
Marked as reachable, this situation can be further divided into two parts. For example, the path obtained from o
is s > g > l > o > r > l > t
, and is can be clearly simplified as s > g > l > t
.
So the reachable paths are sorted by the distance sum, and only the top K paths are kept. The rest are pruned. For the illustration, the K = 3 and paths with distance sum 11
, 12
, 14
are kept as potential search space. See figure (d).
In actual implementation, vertices and edges that not presented in the first SSSP result can be pruned immediately, which helps to speed up the next SSSP computation.
This also applies to the second (reversed) SSSP, which can speed up the CSR format conversion.
CSR Representation of Sparse Graph
CSR (Compressed Sparse Row) is also used to represent the graph. The CSR representation is a common way to store a sparse matrix, whereas a graph can be viewed as an adjacency matrix.
Handon Experiment & Some Thoughts
I tried to run the provided code on my own machine, the testing script can be found at the appendix.
The testing script includes:
 Graph generation with
PaRMAT
 Graph conversion to CSR format (
make_csr
)  Reachable pairs generation (
make_reachable_src_dest
)  Running the
PeeK
algorithm with different threads
The above figure shows the percentage of the CSR conversion time over the total time. It is clear that, for a single threaded PeeK
implementation, the CSR conversion time takes a significant part. Moreover, this part increases as the graph grows more dense. (Note that the fist point have sparsity rate of 97.98%, and the last point have 1.01%.) And actually, the running time of the PeeK
algorithm is growing exponentially as the sparsity rate drops.
Understanding 1
The PeeK
algorithm works better on a sparse graph. This also matches the behavior of K upper bound pruning – the more sparse the graph is, the more vertices and edges can be pruned.
Additionally, running make_csr
would consume extreme large memory, and it can be observed that the memory consumption will grow to a peak and gradually decrease. For such memorybound computation, memory size and access are also potential bottlenecks.
Understanding 2
The CSR conversion time is potentially a bottleneck for the PeeK
algorithm. However, converting a graph to CSR format is also difficult to be parallelized.
For the multithreaded PeeK
implementation, CSR conversion time is relatively less weighted, which looks good. However, the running time is actually 50 to 300 times slower than the single threaded implementation. This is not expected, and I think it is due to the overhead of the multithreading. Probably threadwise communication and synchronization are the main reasons.
Understanding 3
The overhead of the multithreading is not negligible for relatively smaller graph. The multithreading is not always the best choice.
For the experiment and comparison section in the paper, it seems that the make_csr
part is not counted in its running time. This is a potential issue, as the CSR representation of graph is significant for the PeeK
algorithm, and its running time is not negligible.
Bug found
For a graph without enough paths to meet the K requirement, current implementation will fall into an infinite loop at make_reachable_src_dest
. For example, a graph with 100 vertices and 100 edges, the PeeK
algorithm try to meet K = 128
and loop forever.
Although the number of edges can not represent the number of possible paths, it still demonstrates the potential bug in the implementation.
Appendix
Source code of the testing script:
1 
