30000字硕士毕业论文网络中ToP_k查询方法的描述与实现
论文类型：硕士毕业论文
论文字数：30000字
论点：节点,算法,查询
论文概述：
背景由于P2P网络没有中心服务器，不会因为访问中心服务器造成网络拥塞，这种无可替代的优势引起了很大的研究热潮。随着计算机硬件和软件性能的提高，发出的请求在所有节点上都可以进行
论文正文：
1绪论 1.1背景由于P2P网络没有中心服务器，不会因为访问中心服务器造成网络拥塞，这种无可替代的优势引起了很大的研究热潮。随着计算机硬件和软件性能的提高，发出的请求在所有节点上都可以进行计算和处理，这也是P2P网络最大的优点。P2P的应用广泛，在用户间协作，资源共享和网格计算等发面都发挥了很重要的作用。P2P网络同时还可以增强整个计算机系统的可靠性和容错能力。目前大部分P2P研究都假定所有节点带宽和处理能力是一样的，但P2P网络中存在着处理能力和性能都不同的节点，具有较强计算能力和较大带宽的节点被称为超级节点。考虑到这种差异性，在动态网络中把所有的节点都看成一样是很不合理的。面对日益丰富的信息资源，用户在获取信息上面希望能够从海量数据中迅速找到少量最具有价值的信息，而不用让用户从头至尾的逐一挑选[’]。这种用户需求推动了业务系统在信息处理方式上的转变。许多数据密集型应用己不再追求搜索结果的完整性，而只关注如何从海量的数据中快速查询用户最为关心的少量信息。Top-k查询是根据用户指定的聚集函数(单调)从数据集中检索出函数值最高的前k个结果。例如当前点击量在前10名的网站。 在许多数据密集型应用中，普遍存在的用户需求是快速搜索用户最为关心的少量结果。这个问题在信息检索领域得到了很好的应用与研究。例如，在使用搜索引擎时，用户都能在返回的页面中找到想要的结果。针对该问题，上世纪90年代末，Fagin等人借鉴信息检索相关技术的思想，提出了top-k查询的概念。Top-k查询的核心思想是用户只关心数据中极少量的数据，查询引擎只需要找出这些少量数据即可，由此优化查询处理算法，减少带宽消耗并提高查询处理效率。2问题的提出和研究内容Top-k查询也是当今搜索的热点问题，Top-k查询就是查找最满足查询的k个结果。Top-k不关心满足查询条件的所有结果，只是关心满足条件的前k个结果，极大的减少了查找的时间，只要满足条件的Top-k结果出现后，即可停止查询。由于P2P网路的动态性和可扩展性，为P2P网络中的Top一查询带来了一些挑战。如何在提高准确率的同时，尽量减少带宽消耗和减少访问节点的个数，已经成为一个重要的思考问题。基于聚集排序的top-k查询:目前top-k搜索查询的主流技术是以TA算法为代表的基于聚集排序的top-k查询。其核心思想是对每一个对象按照属性评价的降序进行排序，然后采用随机访问和顺序访问这两种方式在各个节点数据序列上获取数据，计算已访问对象的聚集函数值，并利用顺序访问的边界闭值来判断top-k查询是否可以结束，其中顺序访问是指对己排序序列自顶向下的依次访问，随机访问是指从其他节点序列中获取某个对象的值。 P2P网络中基于文件内容的top-k搜索:首先根据先验概率在父亲节点上利用直方图计算其子节点查询的可能上限，按照节点可能上限从大到小排序，依次在节点本地利用向量空间模型进行本地的top-k查询，更新父节点的top-k结果，同时排除非法节点。基于文件内容的top-k检索其优点是利用直方图结构可以剪裁非法节点，其主要缺点由于存在损失函数致使可能上限估计不准，排除一些有效节点，同时每个节点都上传top-k结果给其父节点，造成带宽消耗。总之，目前为止要解决的主要问题:(1)检索数据时的带宽消耗(2)Top-k检索数据的准确率(3)Top-k检索时间本文主要是对P2P网络的拓扑结构进行分析，针对P2P网络的Top-k算法进行了改进，对超立方体拓扑结构模型进入了深入的分析，并且依据超级立方体的拓扑结构实现更高效的top-k算法。1.3论文章节组织结构第一章，即本章，介绍了P2P网络的发展现状和问题;第二章回顾了P2P的发展历程，阐述了P2P的概念，分析了P2P系统的特点，对P2P网络的拓扑结构作了初步的介绍，指出了P2P网络的前景应用;第三章介绍了top-k查询的概念以及现存的比较经典的top-k算法;第四章针对目前算法出现的问题引入了新的top-k查询算法，首先提出了HNUTA算法，通过位置标准和分值标准结合确定不同节点闭值，达到节省带宽的目的。其次提出了基于超立方体结构的CRNTop-k搜索算法，该算法利用展开树将Top-k查询消息广播到所有的节点，每个节点合并自己与子孙节点的查询结果以形成最优的k个资源，在父节点合并结果，根节点获得Top-k结果集。通过动态调整估计上限来减少有效节点的误删除，并限制返回结果的个数来减少带宽消耗;第五章主要针对前一章所提出的两个算法进行了模拟实验，分析了算法的性能，并对改进前后算法的模拟结果进行了对比分析;最后提出了今后需进一步研究的方向。 参考文献[1」邓波.分布式序敏感查询处理关键技术研究[D].长沙:国防科学技术大学，2006.[2〕庄明.基于P2P的路由选择技术研究〔D].上海:上海大学，2005.[3〕徐传运，张杨，毛华扬.P2P全文搜索引擎中的路由算法「J].计算机工程，2008, 34 (17) : 85-87. Risson J, Moors T. Survey of research towards robust peer-to-peer networks: Search methods[J].Computer Networks, 2006, 50 (17):3485-3521. Joung YJ, Yang LW. Wildcard search in structured peer-to-peer networks[J].IEEE Trans. on Knowledge and Data Engineering, 2007,19(11):1524-1540. Zeinalipour-Yazti D, Kalogeraki V, Gunopulos D. pFusion:A P2P architecture forInternet-scale content-based search and retrieval[J].IEEE Trans. on Parallel Distributed Systems, 2007, 18 (6):804-817.张一鸣，卢锡城，郑倩冰一种面向大规模P2P系统的快速搜索算法[J].软件学报，2008, 19 (6)1473-1480.[8〕方启明，杨广文，武永卫.基于P2P的Web搜索技术[J].软件学报，2008, 19 (10) : 2706-2719.[9〕杨天路，刘字宏，张文.P2P网络技术原理与系统开发案例「M].北京:人民邮电出版社，2007.[10」庄雷，潘春简，郭永强.Gnutella网络的连接管理[J].软件学报，2005, 16 (4) :540-551. P. Druschel, A. Rowstron. Past:A large-scale, persistent peer-to-peer storageutility[C].The Eighth IEEE Workshop on Hot Topics in Operating Systems (HotOS-VISchoss Elmau, Germany, 2001:75-80.[12] Kubiatowicz J, Bindel D, Chen Y, et al. OceanStore: an architecture for global-scalepersistent storage[C].The Ninth international Conference on Architectural Supportfor Programming Languages and [13] Ratnasamy S, Francis P, Handler M, et al. A scalable content-addressable network[C]. ACM SIGCOMM, San Diego, CA, 2001:161一172.[14] Stoica I, Morris R, Karger D, et al. Chord: A scalable peer-to-peer lookup servicefor Internet applications[C].ACM SIGCOMM\' O1, San Diego, CA, 2001:149-160.[15] A. Rowstron, P. Druschel. Pastry:Scalable, distributed object location and routin for large-scale peer-to-peer systems[C].IFIP/ACM Middleware 2001, Heidelberg,Germany, 2001:329-350.[16] Zhao BY, Kubiatowicz J, Joseph AD. Tapestry:An infrastructure for fault-toleran wide-area location and routing[R].Technical Report UCB/CSD-Ol一1141, Computer ScienceDivision, U. C. Berkeley, 摘要 4-5 Abstract 5 1 绪论 8-10 1.1 背景 8 1.2 问题的提出和研究内容 8-9 1.3 论文章节组织结构 9-10 2 P2P网络的top-k查询 10-25 2.1 P2P概述 10-16 2.2 Top-k查询 16-21 2.2.1 TA算法 17-18 2.2.2 TPUT算法 18-19 2.2.3 分布式 P2P环境下的非聚合式 Top-k查询模型 19-21 2.3 基于哈希的编码技术 21-24 2.3.1 哈希函数概述 21-22 2.3.2 BloomFilter技术 22-24 2.4 本章小结 24-25 3 混合非一致阈值聚合 HNUTA top-k搜索算法 25-35 3.1 HNUTA算法的基本思想和数据结构 26-27 3.2 HNUTA算法描述 27-34 3.2.1 估计topKvalue 29-31 3.2.2 重新确定阈值 31-33 3.2.3 patch阶段 33-34 3.2.4 获得结果 34 3.3 本章小结 34-35 4 基于超立方体结构 P2P网络中的CRNtop-k搜索算法 35-41 4.1 以超立方体作为 P2P的拓扑结构 35-37 4.1.1 基于超立方体模型的P2P路由算法 35-36 4.1.2 以超立方体为拓扑结构的top-k查询 36-37 4.2 CRNTop-k算法 37-40 4.2.1 VSM 37-38 4.2.2 CRNTop-k算法 38-40 4.3 本章小结 40-41 5 模拟实验及性能分析 41-50 5.1 实验所用数据集 41 5.2 实验平台配置 41 5.3 实验结果及分析 41-49 5.3.1 HNUTA算法 42-43 5.3.2 CRNTop-k算法 43-49 5.4 本章小结 49-50 结论 50-51 参考文献 51-54 攻读硕士学位期间发表学术论文情况 54-55