An Efficient Algorithm for Web Services Composition with a Chain Data Structure

Automatic composition of Web services has drawn a great deal of attention recently. Current Web service (WS) composition algorithms are not only logical presented in a rough way, but also existed inefficient or limited applied scope problem. In this paper a data structure called WS chain table, which describes the dependent relations among Web services, is proposed, and an efficient algorithm for WS composition is developed based on the data structure. The time complexity of the new algorithm is O(max(log m,n)), improved the known O(n times log m) one, where n is the number of WSs and m denotes the number of output parameters of WSs. Experiments are carried out in order to compare the performance of the algorithms with different data structure