Efficient Service Skyline Computation for Composite Service Selection

Service composition is emerging as an effective vehicle for integrating existing web services to create value-added and personalized composite services. As web services with similar functionality are expected to be provided by competing providers, a key challenge is to find the “best” web services to participate in the composition. When multiple quality aspects (e.g., response time, fee, etc.) are considered, a weighting mechanism is usually adopted by most existing approaches, which requires users to specify their preferences as numeric values. We propose to exploit the dominance relationship among service providers to find a set of “best” possible composite services, referred to as a composite service skyline. We develop efficient algorithms that allow us to find the composite service skyline from a significantly reduced searching space instead of considering all possible service compositions. We propose a novel bottom-up computation framework that enables the skyline algorithm to scale well with the number of services in a composition. We conduct a comprehensive analytical and experimental study to evaluate the effectiveness, efficiency, and scalability of the composite skyline computation approaches.