Asymptotic-Efficient Algorithms for Skyline Query Processing over Uncertain Contexts
Jiping Zheng, Yongge Wang, Haixiang Wang, Wei Yu · 2014
Skyline queries are usually associated with user preferences which are dependent on his/her current contexts. For most contexts are from sensing devices, uncertainty is along with the contexts. In this paper, asymptotic-efficient skyline query processing algorithms over uncertain contexts are proposed. First possible world semantics model is utilized to model uncertain contexts as well as uncertain contextual preferences. Since exact skyline algorithm is a #P-hard problem, two heuristic skyline algorithms LHSA, CHSA are proposed to reduce the number of possible worlds not contributing to final skyline query results. To improve the efficiency of skyline query processing under user specified precision, two Monte Carlo Sampling based approximation algorithms 2PMA, S2PMA are proposed. Finally, extensive experimental results show that LHSA and CHSA algorithms can reduce the number of possible worlds to a large extent and the proposed 2PMA and S2PMA algorithms perform more efficiently than heuristic algorithms while S2PMA algorithm is prior to 2PMA with smaller absolute errors.