Research Article
Parallel and Memory-Efficient Realization of KSP/KNN Algorithm
@INPROCEEDINGS{10.1109/CHINACOM.2009.5339879, author={Rongrong Qian and Tao Peng and Yuan Qi and Wenbo Wang}, title={Parallel and Memory-Efficient Realization of KSP/KNN Algorithm}, proceedings={ChinaCom2009-Signal Processing for Communications Symposium}, publisher={IEEE}, proceedings_a={CHINACOM2009-SPC}, year={2009}, month={11}, keywords={}, doi={10.1109/CHINACOM.2009.5339879} }- Rongrong Qian
Tao Peng
Yuan Qi
Wenbo Wang
Year: 2009
Parallel and Memory-Efficient Realization of KSP/KNN Algorithm
CHINACOM2009-SPC
IEEE
DOI: 10.1109/CHINACOM.2009.5339879
Abstract
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.
Copyright © 2009–2024 IEEE
