Cloud computing promises a scalable infrastructure for processing big data applications such as medical data analysis. Cross-cloud service composition provides a concrete approach capable for large-scale big data processing. However, the complexity of potential compositions of cloud services calls for new composition and aggregation methods, especially when some private clouds refuse to disclose all details of their service transaction records due to business privacy concerns in cross cloud scenarios. Moreover, the credibility of cross-clouds and on-line service compositions will become suspicional, if a cloud fails to deliver its services according to its “promised” quality. In view of these challenges, we propose a privacy-aware cross cloud service composition method, named Hire Some-II (History record-based Service optimization method) based on its previous basic version Hire Some-I. In our method, to enhance the credibility of a composition plan, the evaluation of a service is promoted by some of its QoS history records, rather than its advertised QoS values. Besides, the k-means algorithm is introduced into our method as a data filtering tool to select representative history records. As a result, Hire Some-II can protect cloud privacy, as a cloud is not required to unveil all its transaction records. Furthermore, it significantly reduces the time complexity of developing a cross-cloud service composition plan as only representative ones are recruited, which is demanded for big data processing. Simulation and analytical results demonstrate the validity of our method compared to a benchmark.