An efficient parallelization method of Dempster-Shafer evidence theory based on CUDA

The Dempster-Shafer (D-S) evidence theory is effective for uncertain reasoning; it does not require advanced information. The theory has been widely used in multi-sensor data fusion. However, the time complexity of fusing r pieces of evidence for n possible events using Dempster's combination rule is (r - 1) x 2(2n+1), which is considerable. In addition, none of the existing implementations of Dempster's rule directly utilize the parallel performance of GPUs. In this study, an efficient parallelization method for implementing the D-S evidence theory, based on event-based binary encoding and kernel functions on GPUs, was developed. Theoretical analysis and simulation experiments show that the proposed method achieves a speedup of (r-1)2(n)/inverted right perpendicularlog(2) rinverted left perpendicular, thereby reducing the time complexity of Dempster's rule effectively.

Automated summary

The Dempster-Shafer evidence theory is an effective method for uncertain reasoning and is widely used in multi-sensor data fusion. However, the time complexity of fusing multiple pieces of evidence using Dempster's combination rule is considerable, and existing implementations do not fully utilize the parallel performance of GPUs. In this study, a method based on event-based binary encoding and kernel functions on GPUs was developed, achieving a significant reduction in the time complexity of Dempster's rule.