Parallel and Memory-Efficient Realization of KSP/KNN Algorithm

Rongrong Qian; Tao Peng; Yuan Qi; Wenbo Wang

ChinaCom2009-Signal Processing for Communications Symposium

Research Article

Parallel and Memory-Efficient Realization of KSP/KNN Algorithm

Cite: BibTeX Plain Text

@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

Rongrong Qian¹^,*, Tao Peng¹^,*, Yuan Qi¹^,*, Wenbo Wang¹^,*

1: Key Lab. of Universal Wireless Communication, Ministry of Education, Beijing Univ. of Posts and Telecommunications (BUPT) Beijing, China

*Contact email: rongrongqian@bupt.edu.cn, pengtao@bupt.edu.cn, qiyuan@bupt.edu.cn, wbwang@bupt.edu.cn

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.

Published: 2009-11-20
Publisher: IEEE
Modified: 2010-05-16

: http://dx.doi.org/10.1109/CHINACOM.2009.5339879