Stochastic Skyline Operator

Publisher:
IEEE
Publication Type:
Conference Proceeding
Citation:
2011 IEEE 27th International Conference on Data Engineering, 2011, pp. 721 - 732
Issue Date:
2011-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005461OK.pdf323.31 kB
Adobe PDF
In many applications involving the multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions. As a key feature, the skyline in a multi-dimensional space provides the minimum set of candidates for such purposes by removing all points not preferred by any (monotonic) utility/scoring functions; that is, the skyline removes all objects not preferred by any user no mater how their preferences vary. Driven by many applications with uncertain data, the probabilistic skyline model is proposed to retrieve uncertain objects based on skyline probabilities. Nevertheless, skyline probabilities cannot capture the preferences of monotonic utility functions. Motivated by this, in this paper we propose a novel skyline operator, namely stochastic skyline. In the light of the expected utility principle, stochastic skyline guarantees to provide the minimum set of candidates for the optimal solutions over all possible monotonic multiplicative utility functions. In contrast to the conventional skyline or the probabilistic skyline computation, we show that the problem of stochastic skyline is NP-complete with respect to the dimensionality.
Please use this identifier to cite or link to this item: