道路网多用户偏好Top-k天际线查询方法

Multi-User Preference Top-k Skyline Query Method Based on Road Network

已有的天际线(Skyline)查询主要聚焦于单用户场景,并基于单用户模型进行Skyline计算,而较少考虑道路网环境下多用户情况.为了弥补已有方法无法解决道路网络环境下多用户偏好和权重Top-k Skyline查询问题的不足,提出了一种基于道路网环境下多用户偏好Top-k Skyline(multi-user preference Top-k Skyline,MUP-TKS)查询方法.在道路网环境下考虑多用户的不同偏好和权重进行Skyline查询,可以快速得到符合查询用户群偏好和权重的结果集,提供用户群更好的决策支持.MUP-TKS首先通过所提的G_DBC算法,利用道路网中数据点与查询点之间的位置关系和新的索引结构Vor-R*-DHash剪枝、过滤数据点,从而得到距离较优集;再利用静态Skyline集不变的性质,预先计算、保存该集合;然后通过所提的新支配关系对距离较优集与静态Skyline集取并集后的集合S进行放松支配;最后利用所提TK_DC算法对经过放松支配后的候选结果集打分,依据数据点得分情况,排序输出Top-k个结果集返回用户群.理论研究与实验表明,所提方法具有较好的效率与可靠性.

Existing Skyline query most foucus on single-user scenarios,and caculate Skyline results based on single-user model.But less consideration is given to multi-user model in road network environment.The existing methods cannot solve the Top-k Skyline query problem that comprehensively considers multi-user preference and weight in road network environment.Therefore,we propose a Top-k Skyline query method MUP-TKS,based on multi-user preference in road network environment.In this environment,the different preference and weight of multi-user are considered for Skyline calculation.The result set which conforms to the preference and weight of the query user group can be obtained quickly to make better decision.Firstly,through the proposed algorithm G_DBC,the position relation of data points and query points in the road network,and the new index structure Vor-R*-DHash are used for pruning the data points.Thus the optimal distance set is obtained.Then taking advantage of the invariable property of the static Skyline set to precompute and save the set.KPRD algorithm is performed on S set,the union of the optimal distance set and static Skyline set.Finally,TK_DC algorithm is used to score the candidate set.According to the score of the data points,the Top-k of the sorted set are returned to the query user group.Theoretical studies and experiments show that the proposed method is efficient and reliable.