On the computational complexity of Dempster’s Rule of combination, a parallel computing approach

• Published in: Journal of computational science 2021-03, Vol.50, p.101283, Article 101283
• Main Authors: Benalla, Mohammed, Achchab, Boujemâa, Hrimech, Hamid
• Format: Article
• Language: English
• Subjects: Computational complexity; Conquer and divide algorithms; Dempster–Shafer theory; Parallel computing; Thrust CUDA
• ISSN: 1877-7503; 1877-7511
• DOI: 10.1016/j.jocs.2020.101283

Multisensor data fusion with Dempster–Shafer (D–S) theory is beneficial for context inference without any advanced information. D–S theory includes reasoning based on Dempster’s rule of combination of degrees of belief based on different pieces of evidence. Although, the computational complexity of Dempster’s rule of combination is enormous. Any change in the number of pieces of evidence or hypotheses causes a lot of additional computations. Dempster’s rule of combination is shown to be #P-complete. The combination rule of k frames of evidence with nk elements, such that (k∈N|k≥2) has a time complexity of O(2N), where N=∑knk. In this paper, we propose a parallel computing approach for Dempster’s rule of combination based on the concept of conquer and divide algorithms. The proportion of task benefiting from improvement is p=1−2k, hence k2 of theoretical maximum speed-up according to Amdahl’s law. We have tested our algorithm in different experimental settings and observed that the new parallel computing approach has not only achieved the best results in CPU version, but has also outperformed GPU version using Thrust CUDA in almost scenarios of the experiment. •Proposal of a parallel computing approach for Dempster’s rule of combination based on the concept of conquer and divide algorithms, inspired from the spawning technique of a single-celled bacterium.•An improvement of computing performance of p=1−2k, where k is the number of frames of evidence, hence k2 of theoretical maximum speed-up.•The parallel computing approach delivers quite significant performance at CPU version and outperforms GPU version using Thrust CUDA.