Relaxing the Sky: Handling Hard User Constraints in Skyline Service Selection

Recently, the notion of skyline is widely adopted for QoS-based service selection. In many settings, however, users put hard constraints on the QoS parameters. The constrained skyline may thus return an empty result or miss interesting services, resulting in user discontent. In this paper, we propose the concept of regret constrained skyline, which is a relaxation of the constrained skyline, avoiding the aforementioned issue. Moreover, we show how existing skyline algorithms can be adapted to compute the regret constrained skyline and propose a more efficient algorithm. Experimental evaluation conducted on real datasets demonstrates both the effectiveness of the regret constrained skyline and the efficiency of our algorithm.