Scalable optimized composition of web services with complexity analysis

Rattikorn Hewett, Phongphun Kij Sanayothin, Bach Nguyen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

This paper addresses a fundamental issue of web service composition. We present a simple but powerful conceptual model that leads to a scalable approach to automatically constructing a composite web service to meet its requirements by using as few services as possible. Our approach is based on a state space model that has a monotone property to allow efficient search along with efficient algorithms for pruning and simple parallelization. We provide both empirical and theoretical analyses of the proposed approach and show that it has time complexity ofO(n 2), for a repository with n services. However, the approach takes linear time for sequential compositions when service applicability is performed by service discovery and thus, it is shown to give asymptotically optimal performance. Although optimality in the number of services deployed is not guaranteed, our experiments on public benchmark data sets show correct optimized solutions 100% of the time, with a reduction in the average running time, compared to a well-performed planning-based system, of better than 35% over 207 composition problems.

Original languageEnglish
Title of host publication2009 IEEE International Conference on Web Services, ICWS 2009
Pages389-396
Number of pages8
DOIs
StatePublished - 2009
Event2009 IEEE International Conference on Web Services, ICWS 2009 - Los Angeles, CA, United States
Duration: Jul 6 2009Jul 10 2009

Publication series

Name2009 IEEE International Conference on Web Services, ICWS 2009

Conference

Conference2009 IEEE International Conference on Web Services, ICWS 2009
CountryUnited States
CityLos Angeles, CA
Period07/6/0907/10/09

Fingerprint Dive into the research topics of 'Scalable optimized composition of web services with complexity analysis'. Together they form a unique fingerprint.

  • Cite this

    Hewett, R., Sanayothin, P. K., & Nguyen, B. (2009). Scalable optimized composition of web services with complexity analysis. In 2009 IEEE International Conference on Web Services, ICWS 2009 (pp. 389-396). [5175848] (2009 IEEE International Conference on Web Services, ICWS 2009). https://doi.org/10.1109/ICWS.2009.95