Parallel and memory-efficient realization of KSP/KNN algorithm

Many memory-intensive algorithms can actually be designed to parallel realizations through constructing the memory hierarchy. Base on this thought, we disassemble the K-shortest paths/K-nearest-neighbors (KSP/KNN) problem to small subproblems and use Yen´s method to treat with each subproblem, therefore derive a new method to resolve the KSP/KNN problem, which can easily be realized in parallel computing and named as Memory Hierarchical Yen´s (MHY) method. We evaluate MHY analytically and numerically. The numerical results demonstrate that MHY can even greatly reduce memory cost comparing with the original Yen´s method.