论文部分内容阅读
近年来,随着互联网技术发展,同构对称发布/订阅系统的应用也越来越普及。由于在同构对称发布/订阅系统中,产生的候选环匹配结果集很大,特别是在大型的系统中,可能是海量的,不利于用户对候选结果的选择利用。如何快速、高效的为用户推荐k个最优的候选环匹配是同构对称发布/订阅系统中研究的关键问题之一。在同构对称发布/订阅系统的不同应用中,有时匹配结果可以调用打分函数为其打分,依据分值排序求出前k个最优的。有时无法调用打分函数打分,不能对其排序。为此本文分别提出了面向匹配结果不可排序的Top-k查询算法和面向匹配结果可以排序的Top-k查询算法。 针对匹配结果不能通过调用打分函数打分的问题,本文对相关的基础理论工作分析与总结,寻求解决问题的相关技术。提出了基于k-支配Skyline查询的面向匹配结果不可排序的Top-k查询算法。首先扩展了同构对称发布/订阅模型;然后对算法基本思想以及基本操作做了详细的描述;最后,本文在模拟环境中对算法做了多种评估分析比较试验,从订阅数量、维度、数据分布、选择度等方面分析实验结果,实验表明本文提出的算法查全率和查准率都在94%以上。 匹配结果可以通过调用打分函数打分时,打分函数复杂度不同算法性能可能也不一样。本文针对高复杂度的打分函数,提出了基于高复杂度打分函数的面向匹配结果可以排序的Top-k查询算法。该算法策略是基于在计算机中一次比较运算时间效率优于一次算术运算。所以本算法核心就是减少了调用打分函数的次数,打分函数复杂度较高时,候选匹配各维上比较一次的操作总运算时间代价优于调用一次打分函数的时间代价。本文最后从订阅数量、打分函数复杂度、选择度、维度等方面对算法性能做了评价。基于高复杂度打分函数的面向匹配结果可以排序的Top-k查询算法的在打分函数复杂度越高,时间性能优势越明显。