P2P网络中的Anytime查询处理

论文摘要

P2P网络具有高可扩展性、健壮性、自主性等优点,被广泛应用。结构化的P2P数据管理系统具有结构化P2P网络的优点,可以为数据管理用户应用提供具有以上优点的服务。现有的结构化P2P数据管理查询技术可以良好的解决基于关键字的等值查询和范围查询,然而一些更为复杂的查询,如多维范围查询、top-k查询、KNN查询、join查询、skyline查询等,还没有得到很好的解决方法。在P2P网络中,如果一个复杂查询涉及的节点数量众多,该查询的代价将十分巨大而且无法避免。本文设计了结构化P2P网络中的anytime查询处理算法,在增量形式地返回查询结果的同时,实时计算当前结果的质量。如果用户对当前结果满意,用户可以随时中止查询处理,减少用户需求之外的查询处理代价。为了实时计算查询处理结果质量,本文设计了HA2-d树存储结构,以及HA2-d树在P2P网络中的动态维护方法,并在HA2-d树中索引多维数据和多维直方图。HA2-d树是一棵平衡二叉树,其中每个节点维护一个多维区域内数据的直方图。由于精确的直方图获取代价太大,本文使用近似聚集的方法,使得HA2-d树所维护的直方图具有较小的误差界限（如5%）。本文设计了多维范围查询、top-k查询和KNN查询处理算法,这些查询处理算法基于HA2-d树存储结构。我们定义了HA2-d树中,两个节点的最高分离树概念,将其用于查询路由决策。本文设计的查询处理算法消息代价为O（M log N）,其中M是含有查询结果的节点数量,N为网络中节点数量。由查询消息代价可见,本文设计的算法具有良好的可扩展性。实验证明本文设计的P2P网络中的anytime查询处理算法的消息代价随网络大小的增长缓慢,具有良好可扩展性。当前结果质量的计算代价在整个查询处理过程中只占据较小份额。因此,本文设计的anytime查询处理算法可以有效的为用户衡量当前结果质量,减少用户需求之外的查询处理代价。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题来源与研究目的和意义
• 1.2 P2P技术简介
• 1.2.1 P2P概念介绍
• 1.2.2 P2P网络特点简介
• 1.2.3 P2P网络结构简介
• 1.3 相关工作文献综述
• 1.4 本文主要研究内容
• 1.5 本文组织结构
• 1.6 本章小结
• 第2章 P2P查询处理技术研究
• 2.1 P2P网络拓扑技术研究
• 2.1.1 非结构化拓扑
• 2.1.2 结构化拓扑
• 2.1.3 超节点拓扑结构
• 2.2 P2P查询路由技术研究
• 2.2.1 非结构化拓扑查询路由
• 2.2.2 结构化拓扑查询路由
• 2.3 本章小结
• 第3章 数据存储系统设计
• 3.1 引言
• 3.2 P2P网络中2-d树存储结构的实现
• 3.2.1 预备知识VBI-Tree
• 3.2.2 P2P网络中的2-d树多维索引
• 3.3 P2P网络中HA2-d树结构的实现
• 3.3.1 HA2-d树结构
• 3.3.2 HA2-d树在VBI-tree中的实现
• 3.4 HA2-d树动态维护
• 3.4.1 Peer加入
• 3.4.2 节点离开
• 3.5 本章小结
• 第4章 P2P网络中的Anytime查询处理
• 4.1 引言
• 4.2 P2P网络中的anytime范围查询处理
• 4.2.1 问题定义
• 4.2.2 Anytime范围查询处理
• 4.3 P2P网络中的anytime top-k查询处理
• 4.3.1 问题定义
• 4.3.2 Anytime top-k查询处理
• 4.4 P2P网络中的anytime KNN查询处理
• 4.4.1 问题定义
• 4.4.2 Anytime KNN查询处理
• 4.5 HA2-d树对近似聚集查询的支持
• 4.6 本章小结
• 第5章 模拟与仿真实验分析
• 5.1 实验环境配置
• 5.2 P2P网络中Anytime范围查询处理实验结果
• 5.2.1 估计准确率
• 5.2.2 消息代价
• 5.2.3 负载平衡测试
• 5.3 P2P网络中anytime top-k查询处理实验结果
• 5.3.1 消息代价
• 5.3.2 查询涉及节点
• 5.4 P2P网络中anytime KNN查询处理实验结果
• 5.4.1 消息代价
• 5.4.2 查询涉及节点
• 5.5 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢