Abstract:

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.

Key words: context aware, preference, query processing, branch and bound pruning, top-k

摘要： 查询执行时加入场境依赖的用户偏好可以帮助人们从大量信息中发现正确答案。已经证明, 不确定场境信息条件下, 用户偏好的查询可能导致NP 完全或者#P 完全难度的推理难题。提出了一个简单通用的方法优化不确定场境信息条件下的用户偏好查询, 用户查询等价于搜索建立的场境偏好空间(contextual preferences space, CPS)。根据具体应用需求, 考虑了两种搜索方案：搜索最优的元组和返回top-k(k 为用户指定)个元组。采用定量的方法对用户偏好进行建模。为了提高查询处理效率, 提出两种搜索剪枝策略：边界剪枝(branch and bound searching, BBS)和偏序边界剪枝(partial value branch and bound space searching, pBBS)。最后, 从I/O 访问次数和CPU 运行时间两个角度评价所提出的方法。

关键词: 场境感知, 偏好, 查询处理, 边界剪枝, top-k