Branch and Bound Pruning Based Preference Query Processing Techniques under Uncertain Contexts
Jiping Zheng · 2011
Query execution combined with context-dependent preferences makes people possible to get right results in current information abundance society.It has been proved that evaluating user preference queries on uncertain context information will introduce NP-complete and #P-complete probabilistic inference problems.This paper proposes a simpler and more generalized framework to manage uncertainty for multidimensional contextual preferences.User queries are formulated as searching corresponding tuple(optimal) or tuples(top-k) in the contextual preferences space(CPS).User preferences are modeled in a quantitative way.Two pruning strategies,branch and bound searching(BBS) and partial value branch and bound space searching(pBBS),are provided to accelerate query evaluation processes.Finally,the approaches are evaluated from two perspectives:CPU time and I/Os.