Research On Probabilistic Skyline Query Processing With Context Awareness

In recent years skyline query is an important aspect for queries on uncertain data. Probabilistic skyline queries, as an aspect of queries on uncertain data, have become an important issue. Skyline queries are usually associated with users' preferences and the preferences are depend on users' current contexts. For most contexts are from sensing devices, uncertainty is along with users' contexts. The dissertation studies the probabilistic skyline query processing with context awareness, and the main innovations are as follows:(1) The approximate skyline query processing algorithms over uncertain contexts based on heuristic methods and Monte Carlo sampling mechanisms are proposed. First, possible world semantics model is utilized to model uncertain contexts as well as uncertain contextual preferences,and skyline query semantics based on uncertain contexts are provided. After that, for exact skyline algorithm is a #P-hard problem, two heuristic skyline algorithms, LHSA and C&T, are proposed to reduce the number of possible world instances not contributing to final skyline query results. To improve the efficiency of skyline query processing under user specified precision, two-phase Monte Carlo approximate algorithm PMA and improved two-phase Monte Carlo approximate algorithm MPMA are proposed. Finally, extensive experimental results show that LHSA and C&T algorithms can reduce the number of possible world instances to a large extent and the proposed PMA and MPMA algorithms perform more efficiently than heuristic algorithms while MPMA algorithm is prior to PMA.(2) The main memory tree structure ZB*tree is studied. ZB*tree which is based on ZBtree is a new variant of B*-tree to organize uncertain data according to ordered Z-addresses of instances.ZB*tree strategically links all adjacent sibling nodes which can form a linked list at each depth.Probabilistic skyline queries based on ZB*tree can avoid repeated and unnecessary dominance tests and efficiently improve the performance of Probabilistic skyline queries.(3) The novel probabilistic skyline query on uncertain data over uncertain contexts is studied. We develop a novel probabilistic skyline query on uncertain data over uncertain contexts called UC-PSkyline, where possible world semantics model is utilized to model uncertain contexts. To reduce the number of dominance tests, we devise an main memory tree structure ZB*tree to process UC-PSkyline queries. We also develop pre-processing and pruning techniques that can efficiently improve performance of UC-PSkyline. Comprehensive experiments show the effectiveness andefficiency of the proposed techniques.