Top-k Automatic Service Composition: A Parallel Method for Large-Scale Service Sets

Quality-of-Service (QoS)-aware web service composition is of great importance to assemble individual services into a composite one meeting functional and nonfunctional requirements. Given a large number of candidate services, automatic composition is essential so as to derive a composite service efficiently. Most existing methods return one solution that is optimal in some given criteria. This is somewhat rigid in terms of flexibility. In case some component service in the optimal composition becomes unavailable, the composition algorithm has to run again to find another optimal solution. Also, in a lot of circumstances users prefer multiple alternatives over a single one. Therefore, providing top-k service compositions according to their QoS is becoming more desirable. On another aspect, from the perspective of computation efficiency, due to the explosion of the searching space, single-threaded methods are usually not capable of handling a large number of candidate services. This paper tackles these two issues together, i.e., large-scale, QoS-based services composition yielding top-k solutions. The composition algorithm is based on the combination of backtrack search and depth-first search, which can be executed in a parallel way. Experiments are carried out based on the datasets provided by the WS-Challenge competition 2009 and China Web Service 2011. The results show that our approach can not only find the same optimal solution as the winning systems from these competitions, but also provide alternative solutions together with the optimal QoS. Note to Practitioners-To address the challenge of the automatic composition of web services in a large scale, this work proposes a novel approach to find top-k solutions with optimal global QoS. The problem of service composition is transformed into a graph searching problem. Each composition solution is represented in the form of a directed acyclic graph. The approach is divided into two stages, i.e., the run-up stage and the composition stage. Run-up stage deals with data preprocessing to parse service repository, which can be executed offline. In the composition stage, top-k compositions in response to users' queries are generated in parallel.