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

计算机科学与探索 ›› 2011, Vol. 5 ›› Issue (5): 410-425.

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

郑吉平^1,2, 秦小麟¹, 戴华¹

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

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-01 发布日期:2011-05-01

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

ZHENG Jiping, QIN Xiaolin, DAI Hua

1. Department of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
2. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-01 Published:2011-05-01

摘要/Abstract

摘要： 查询执行时加入场境依赖的用户偏好可以帮助人们从大量信息中发现正确答案。已经证明, 不确定场境信息条件下, 用户偏好的查询可能导致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

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

郑吉平1,2 , 秦小麟1 , 戴华1 . 基于边界剪枝的不确定场境下偏好查询技术[J]. 计算机科学与探索, 2011, 5(5): 410-425.

ZHENG Jiping, QIN Xiaolin, DAI Hua.

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

[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(5): 410-425.

[1]	高仰, 刘渊. 融合知识图谱和短期偏好的推荐算法[J]. 计算机科学与探索, 2021, 15(6): 1133-1144.
[2]	李广丽，滑瑾，袁天，朱涛，邬任重，姬东鸿，张红斌. 基于用户偏好挖掘生成对抗网络的推荐系统[J]. 计算机科学与探索, 2020, 14(5): 803-814.
[3]	韩希先，宋翠，戈韵如，高宏，李建中. 海量数据上有效的top-k Skyline查询算法[J]. 计算机科学与探索, 2019, 13(5): 775-787.
[4]	和凤珍，石进平. 非均匀划分拟阵约束下的多样性推荐方法[J]. 计算机科学与探索, 2019, 13(2): 226-238.
[5]	宋雨萌，陈默，于戈. 时序地理社交网络中基于动态偏好的组查询[J]. 计算机科学与探索, 2019, 13(11): 1813-1828.
[6]	张以文，艾晓飞，崔光明，钱付兰. 联合用户兴趣矩阵及全局偏好的推荐算法[J]. 计算机科学与探索, 2018, 12(2): 197-207.
[7]	郭宁宁，王宝亮，侯永宏，常鹏. 融合社交网络特征的协同过滤推荐算法[J]. 计算机科学与探索, 2018, 12(2): 208-217.
[8]	单晓欢，王广香，宋宝燕，丁琳琳，许岩. 大规模动态图中标签约束的频繁子图Top-K查询[J]. 计算机科学与探索, 2018, 12(11): 1740-1747.
[9]	刘慧婷，黄厚柱，刘志中，赵鹏. 基于分割的字符串相似性查找算法[J]. 计算机科学与探索, 2018, 12(1): 120-133.
[10]	陈震鹏，陆璇，李豁然，刘譞哲. 多维应用特征融合的用户偏好预测[J]. 计算机科学与探索, 2017, 11(9): 1405-1417.
[11]	郭心宇，岳昆，李劲，武浩，张彬彬. 面向评价数据中用户偏好发现的证据理论方法[J]. 计算机科学与探索, 2017, 11(2): 231-241.
[12]	孙萍，李锵，关欣，吕杰. 融合评分倾向度和双重预测的协同过滤推荐算法[J]. 计算机科学与探索, 2017, 11(10): 1642-1651.
[13]	尹子都，岳昆，武浩，付晓东，刘惟一. 基于记忆曲线的数据密集型动态用户行为建模[J]. 计算机科学与探索, 2016, 10(10): 1376-1386.
[14]	杨林青，李湛，牟雁超，樊里略，李红燕，王腾蛟，雷凯. 面向大规模数据集的并行化Top-k Skyline查询算法[J]. 计算机科学与探索, 2015, 9(8): 897-905.
[15]	王丽，秦小麟，施常月. 室内双色数据集上的反向最近邻查询[J]. 计算机科学与探索, 2015, 9(3): 310-320.