In the era of big data, data intensive applications have posed new challenges to the field of service composition. How to select the optimal composited service from thousands of functionally equivalent services but different Quality of Service(Qo S) attributes has become a hot research in service computing. As a consequence,in this paper, we propose a novel algorithm MR-IDPSO(Map Reduce based on Improved Discrete Particle Swarm Optimization), which makes use of the improved discrete Particle Swarm Optimization(PSO) with the Map Reduce to solve large-scale dynamic service composition. Experiments show that our algorithm outperforms the parallel genetic algorithm in terms of solution quality and is efficient for large-scale dynamic service composition. In addition,the experimental results also demonstrate that the performance of MR-IDPSO becomes more better with increasing number of candidate services. In the era of big data, data intensive applications have posed new challenges to the field of service composition. How to select the optimal composited service from thousands of functionally equivalent services but different Quality of Service (QoS) attributes has become a hot research in service computing. As a consequence, in this paper, we propose a novel algorithm MR-IDPSO (Map Reduce based on Improved Discrete Particle Swarm Optimization), which makes use of the improved discrete Particle Swarm Optimization (PSO) with the Map Reduce to solve large-scale dynamic service composition. Experiments show that our algorithm outperforms the parallel genetic algorithm in terms of solution quality and is efficient for large-scale dynamic service composition. In addition, the experimental results also demonstrate that the performance of MR-IDPSO becomes more better with increasing number of candidate services.