基于边界剪枝的不确定场境下偏好查询技术  

Branch and Bound Pruning Based Preference Query Processing Techniques under Uncertain Contexts

作　　者：郑吉平[1,2] 秦小麟[1] 戴华[1] 

机构地区：[1]南京航空航天大学计算机科学与技术系,南京210016 [2]南京大学计算机软件新技术国家重点实验室,南京210093

出　　处：《计算机科学与探索》2011年第5期410-425,共16页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金 No.60673127;国家高技术研究发展计划(863) No.2007AA01Z404;江苏省科技支撑计划项目 No.BE2008135~~

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

关 键 词：场境感知 偏好 查询处理 边界剪枝 TOP-K 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]