Computing Service Skyline from Uncertain QoWS

The performance of a service provider may fluctuate due to the dynamic service environment. Thus, the quality of service actually delivered by a service provider is inherently uncertain. Existing service optimization approaches usually assume that the quality of service does not change over time. Moreover, most of these approaches rely on computing a predefined objective function. When multiple quality criteria are considered, users are required to express their preference over different (and sometimes conflicting) quality attributes as numeric weights. This is rather a demanding task and an imprecise specification of the weights could miss user-desired services. We present a novel concept, called p-dominant service skyline. A provider S belongs to the p-dominant skyline if the chance that S is dominated by any other provider is less than p. Computing the p-dominant skyline provides an integrated solution to tackle the above two issues simultaneously. We present a p-R-tree indexing structure and a dual-pruning scheme to efficiently compute the p-dominant skyline. We assess the efficiency of the proposed algorithm with an analytical study and extensive experiments.