学位论文 > 优秀研究生学位论文题录展示

P2P网络中的Anytime查询处理

作　者: 王金宝
导　师: 高宏
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: P2P 分布式查询处理索引结构
分类号: TP393.02
类　型: 硕士论文
年　份: 2008年
下　载: 6次
引　用: 0次
阅　读: 论文下载

内容摘要

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查询处理算法可以有效的为用户衡量当前结果质量,减少用户需求之外的查询处理代价。

全文目录

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

相似论文

Ad-Hoc网络多信道MAC层协议的信道分配问题的研究,TN929.5
分布式系统的故障注入方法研究,TP338.8
并行分布式网络模拟器PDNS容错技术的研究,TP302.8
支持XML数据查询的F&B索引结构的研究,TP311.13
海量多数据库集成系统的查询处理研究,TP311.13
基于NS2的PeerCast模拟平台设计与实现,TP311.52
面向Gnutella和eMule网络拓扑测量和安全性分析,TP393.08
面向海量邮件的检索系统研究与实现,TP393.098
含分布式电源的微电网控制策略研究,TM61
基于聚类分析的P2P流量识别算法的研究,TP393.02
基于移动Agent的分布式网络通信机制的研究,TP393.02
基于分布式环境压力测试问题的研究,TP311.52
一种可视化的分布式数据集成模型的研究与实现,TP311.52
分布式事务处理协议的研究与应用,TP311.13
音像广播远程教育系统中直播服务器的设计与实现,TP311.52
基于Map/Reduce框架的分布式日志分析系统的研究及应用,TP311.52
基于Oracle的移动彩铃分布式数据库设计与实现,TP311.13
分布式视频编码边信息生成研究,TN919.81
概率XML文档中Holistic Twig查询处理算法的研究与实现,TP311.13
基于P2P流媒体系统的设计与实现,TN919.8
基于分布式三层应用的设备管理信息系统的开发和研究,TP311.52