同构对称发布/订阅系统近似动态环匹配优化策略的研究与实现

论文摘要

随着互联网和交付服务的发展,物品交换、住房交换、和器官移植等在线交换服务,变得越来越方便和流行。这些在线服务作为同构对称发布/订阅系统的一类应用,在现代贸易和日常生活中起着越来越重要的作用。在同构对称发布/订阅系统的研究中,环匹配算法是关键问题之一。近似动态环匹配策略,用统计学方法分析订阅被匹配概率的分布规律,得到节省存储空间比例的预测公式,进而设定过滤阈值。解决了动态环匹配策略需要存储海量中间结果的问题,但是预测公式并不准确,而且只适用于订阅信息服从均匀分布的情况,为此本文提出了一种适用于任意数据分布的优化的近似动态环匹配策略。本文的优化策略,首先用概率学方法对预测公式的通用性进行优化,提出适用于任意数据分布环境的节省空间比例的预测公式；然后更加精确的分析订阅被匹配概率的分布特点,对预测方法的精度进行优化。同时分析订阅各维数据的分布情况,运用降维策略做进一步优化；最后,本文在仿真环境中做了多种性能验证试验,从数据分布、选择度、维度等方面分析实验结果,实验表明本文的优化策略得到的预测结果更加准确,精确度较未优化的近似动态环匹配策略提高了平均15个百分点。对于发布/订阅系统来说,如何让更多的用户参与匹配使系统利润最大化,以及为用户推荐前k个最优的环匹配以提高用户的满意度,是必要的也是有意义的。系统最优算法很好的解决了系统利润最大化的问题,能够得到包含最多订阅的环匹配结果集。但是关于为用户推荐前k个最优的候选匹配的研究很少。本文从面向用户的角度,首先扩展同构对称发布/订阅模型,设计候选环匹配质量的评价方法；然后提出了基于堆的top-k算法和基于败者树的top-k算法,并且从理论上论证了算法的可行性。最后本文从订阅数量、选择度、维度等方面对top-k算法性能做了验证,实验表明,基于败者树的top-k算法当选择度越大、订阅数越多、维度越小,与基于堆的top-k算法相比,性能越好。同时在有资源限制时,基于败者树的top-k算法具有更好的准确度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 问题的提出及意义
• 1.3 本文主要的工作
• 1.4 本文组织结构
• 第2章 相关工作
• 2.1 发布/订阅系统概述
• 2.1.1 发布/订阅系统的拓扑结构
• 2.1.2 发布/订阅系统的形式化描述
• 2.2 发布/订阅系统的环匹配算法
• 2.3 层次分析法
• 2.4 top-k算法
• 2.5 本章小结
• 第3章 优化的近似动态环匹配策略
• 3.1 相关定义
• 3.2 近似动态环匹配的naive策略
• 3.2.1 订阅被匹配的概率
• 3.2.2 抛出链的位置
• 3.2.3 节省空间比例的预测方法
• 3.3 优化的近似动态环匹配策略
• 3.3.1 预测方法的通用性优化策略
• 3.3.2 预测方法的精度优化策略
• 3.3.3 降维优化策略
• 3.4 性能验证
• 3.4.1 实验环境
• 3.4.2 实验结果及分析
• 3.5 本章小结
• 第4章 面向用户的top-k算法
• 4.1 相关定义及模型扩展
• 4.1.1 相关定义
• 4.1.2 模型扩展
• 4.1.3 订阅属性权重的分配策略
• 4.1.4 订阅匹配度的计算方法
• 4.2 基于堆的面向用户的top-k算法
• 4.2.1 相关概念
• 4.2.2 基本思想
• 4.2.3 算法描述
• 4.2.4 算法性能分析
• 4.3 基于败者树的面向用户的top-k算法
• 4.3.1 基本思想
• 4.3.2 算法描述
• 4.3.3 算法性能分析
• 4.4 对称性检验算法
• 4.5 性能验证
• 4.5.1 实验环境
• 4.5.2 实验结果及分析
• 4.6 本章小结
• 第5章 结束语
• 5.1 内容总结
• 5.2 未来展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文和参加的项目