MapReduce particle filtering with exact resampling and deterministic runtime

Area of Science:

• Computational Statistics
• Bayesian Inference
• Big Data Analytics

Background:

• Particle filters are powerful Bayesian methods for sequential estimation in complex models.
• Increasing particle count improves accuracy but poses computational challenges for Big Data.
• Existing particle filter implementations lack efficient MapReduce integration.

Purpose of the Study:

• To develop an efficient MapReduce implementation of particle filters.
• To address the resampling component bottleneck in parallel particle filter execution.
• To enable the use of a significantly larger number of particles for improved estimation.

Main Methods:

• Implementation of a particle filter using the MapReduce programming model.
• Development of a novel, approximation-free resampling component for parallel processing.
• Analysis of the resampling component's spatial and time complexity (O(N) and O((logN)^2)).

Main Results:

• A functional MapReduce-based particle filter implementation was successfully developed.
• The new resampling component achieves deterministic O((logN)^2) time complexity.
• Demonstrated scalability with a particle filter using 2^24 particles across 512 cores.

Conclusions:

• The proposed MapReduce particle filter implementation effectively handles Big Data challenges.
• The optimized resampling component significantly improves parallel execution efficiency.
• This work facilitates more accurate sequential estimation in non-linear, non-Gaussian scenarios using Big Data.