（计算机应用技术专业论文）p2p相似搜索中分层索引机制研究.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论 文( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位 论文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可 以将公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目 录检索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开 大学向教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息 研究所和中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相 应学位论文数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论 文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 翅鳌 2 0 1 0 年5 月2 8 日 南开大学研究生学位论文作者信息 论文题目 p 2 p 相似搜索中分层索引机制研究 姓名胡紫学号 2 1 2 0 0 7 0 3 2 8 答辩日期2 0 1 0 年5 月2 8 日 论文类别博士口学历硕+ 硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院专业计算机应用技术 联系电话 l3 8 2 0 8 3 3 7 5 4e m a i l h u z i l u c k y g m a i l c o r n 通信地址( 邮编) ：天津市南开大学两区公寓3 一l - 2 0 2 备注：是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论 文( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位 论文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可 以将公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目 录检索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开 大学向教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息 研究所和中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相 应学位论文数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论 文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 f i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字：尘马鳖 2 0 1 0 年5 月2 8 日 南开大学研究生学位论文作者信息 论文题目p 2 p 相似搜索中分层索引机制研究 姓名胡紫学号 2 1 2 0 0 7 0 3 2 8 答辩日期2 0 1 0 年5 月2 8 日 论文类别博士口学历硕士硕士专业学位口高校教师口同等学力硕士口 专 院系，所 信息技术科学学院计算机应用技术 业 e m 联系电话 1 3 8 2 0 8 3 3 7 5 4 h u z i l u c k y g m a i l c o r n a i l 通信地址( 邮编) ：天津市南开大学西区公寓3 l - 2 0 2 备注：是否批准为非公开论文否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 本人郑重声 取得的研究成果 含任何他人创作 涉及的研究工作 学位论文原创性 学位论文作 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限2 0年月日至2 0年月日 审批表编号批准日期 2 0 年月 日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长l o 年，可少于l o 年) 摘要 摘要 相似搜索已经成为p 2 p 网络研究中的热点问题。m c a n 通过锚点比对的 方式将原始数据空间映射到低维向量空间，然后在低维向量空间上进行数据的 发布和搜索。但是映射过程会造成信息丢失，从而导致m c a n 相似搜索效率 降低。本文提出了一种新的分层索引结构m c a n * 。m c a n 通过对节点在欧 式空间中进行d e l a u n a y 三角剖分，形成底层拓扑结构。并且在此基础上设计了 分层索引结构来实现启发式路由算法以及提高相似搜索的效率。 本文重点研究了m c a n * 分层索引仿真软件的设计与实现。论文系统地阐 述了m c a n * 仿真软件的设计方法与实现技术。该仿真软件基于离散事件队列 模拟多节点的加入和退出行为，实现了局部索引树的维护、系统路由、数据发 布、范围查询、k 近邻查询、节点加入和节点退出等功能。论文详细地介绍了 仿真软件中这几个重要模块算法的流程与代码实现。 本文使用该分层索引仿真软件在c o r d 数据集上测试和分析了m c a n * 的 效率。进行范围查询时，在数据的搜全率仍然保持1 0 0 的前提下，m c a n * 的节点访问率比m c a n 平均降低了3 0 2 ，数据访问率平均降低了3 1 3 。进 行k 近邻查询时，m c a n 的搜索的半径平均比m c a n 缩小了3 7 4 ，平均 节点访问率为m c a n 的4 3 3 ，平均数据访问率为m c a n 的4 3 8 。实验结 果表明m c a n 相似搜索的效率要高于m c a n ，同时也表明该仿真软件能较 好地模拟分层索引系统中节点的行为，可以作为m c a n * 性能评测的工具。 关键词：p 2 p 网络，相似搜索，启发式路由算法，局部索引树 s i m i l a rs e a r c h d a t am e t r i cs p a c ei n t oal o w e rd i m e n s i o nm e t r i cs p a c ew i t ht h em e t h o do f c o m p a r i n g 、】 r i t hp i v o t s ，t h e ns t o r e sa n ds e a r c h e sd a t ai nt h i sl o w e rd i m e n s i o nm e t r i c s p a c e h o w e v e r , t h i sm e t h o dw i l lc a u s et h ei n f o r m a t i o nl o s sd u r i n gt h ep r o c e s so f m a p p i n gw h i c hw i l ll e a dt ot h el o we f f i c i e n c yo fs i m i l a rs e a r c hi nm - c a n i p r o p o s e an o v e lh i e r a c h i c a li n d e xs t r u c t u r em - c a n i nt h i sp a p e r m - c a n b u i l d s u pt h eb o t t o mt o p o l o g yb a s e do nd e l a u n a yt r i a n g u l a t i o n w i t ht h eh i e r a c h i c a li n d e x s t r u c t u r e ，m - c a n c a nr e a l i z et h eh e u r i s t i cr o u t i n gf u n c t i o na n di m p r o v et h e e f f i c i e n c yo ft h es i m i l a rs e a r c h t h ep a p e rm a i n l yf o c u s e so nt h ed e s i g na n di m p l e m e n t a t i o no ft h es i m u l a t i o n s o f t w a r eo fm - c a n 掌a n dd e s c r i b e st h em e t h o da n dt e c h n o l o g yo ft h es i m u l a t i o n s o f t w a r ei nd e t a i l s t h i ss o f t w a r es i m u l a t e sn o d e s j o i n i n ga n dl e a v i n gb e h a v i o u r b a s e do nd i s c r e t ee v e n tq u e u ea n dr e a l i z e st h ef u n c t i o no fl o c a li n d e xt r e e m a i n t a i n i n g ，s y s t e mr o u t i n g ，d a t ap u b l i s h i n g ，r a n g eq u e r y , l 心眦q u e r y , n o d ej o i n i n g a n dn o d el e a v i n g b e s i d e s ，t h ep a p e ra l s od e s c r i b e st h ep r o c e s sa n di m p l e m e n t a t i o n o ft h e s ei m p o r t a n tm o d u l e si nt h es o f t w a r ei nd e t a i l s f i n a l l y , it e s ta n da n a l y z et h ee f f i c i e n c yo fm - c a n o n t h ec o r e ld a t a s e tw i t l i t h i ss i m u l a t i o ns o l , r a r e w h e nm - c a n p e r f o r m sr a n g eq u e r y , t h ea v e r a g en o d e v i s i t i n gr a t i oi sr e d u c e d3 0 2 a n dt h ea v e r a g ed a t av i s i t i o n gr a t i oi sr e d u c e d31 3 ， c o m p a r i n g 埘mm c a n ，w h i l et h ed a t ah i tr a t i os t i l lk e e p s10 0 w h e nm - c a n p e r f o r m sk n nq u e r y , t h ea v e r a g es e a r c h i n gr a d i u si s r e d u c e da b o u t3 7 4 ，t h e a v e r a g en o d ev i s i t i n gr a t i oi so n l y4 3 3 a n dt h ea v e r a g ed a t av i s i t i o n gr a t i oi s 4 3 8 o ft h a ti nm - c a n n er e s u l t ss h o w st h a tm c a n i sm o r ee f f i c i e n c yt h a n m c 蝌a n dt h es i m u l a t i o ns o f t w a r ec a ns i m u l a t en o d e s b e h a v i o ri nt h eh i e r a c h i c a l i n d e xs y s t e ma n dc a nb eu s e da sag o o dt e s t i n gt o o lo fm c a n k e yw o r d s ：p 2 pn e t w o r k ，s i m i l a rs e a r c h ，h e u r i s t i cr o u t i n ga l g o r i t h m ，l o c a l i n d e xt 陀e n 目录 目录 第一章引言1 第一节研究背景1 第二节研究现状2 第三节论文研究内容3 第四节论文结构4 第二章p 2 p 相似搜索研究基础6 第一节p 2 p 网络综述。6 第二节相似搜索概念一7 2 2 1 度量空间8 2 2 2 范围查询8 2 2 3k 近邻查询9 第三节集中式索引1 0 2 3 1m t r e e 1 0 2 3 2s s s t r e e 15 第四节分布式索引16 2 4 1m c a n l6 2 4 2m c h o r d 。l8 2 4 3g h t 2l 第五节分层索引结构m c a n 2 4 2 5 1 问题分析2 4 2 。5 2m c a n 2 5 2 5 3 上层欧式坐标空间索引2 6 2 5 4 下层原始数据空间索引2 7 i i i 2 5 5 2 5 6 2 5 7 第六节本章小结3 6 第三章p 2 p 分层索引仿真软件的设计与实现3 8 第一节软件编写以及运行环境3 8 第二节仿真软件的代码结构3 8 第三节基于离散事件队列的多节点模拟实现3 9 3 3 1 定时器类c t i m e r 。3 9 3 3 2 节点基类c n o d e 4 0 3 3 3 事件驱动类c s c h e d u l e m a n a g e r 4 1 第四节索引树维护模块4 3 第五节路由模块4 6 第六节数据发布模块4 8 第七节范围查询模块4 9 第八节k 近邻查询模块5 3 第九节节点加入模块5 5 第十节节点退出模块5 8 第十一节本章小结6 0 第四章仿真软件在分层索引系统中的应用6 1 第一节数据集。6 1 第二节m c a n * 在c o l o rm o m e n t s 数据集上性能测试6 2 4 2 1 范围查询6 2 4 2 2k 近邻查询6 5 第三节m c a n * 在c o o c c u r r e n c et e x t u r e 数据集上性能测试6 7 4 3 1 范围查询。6 7 i v 目录 4 3 2k 近邻查询6 9 第四节m c a n * 与m c a n 性能比较7 l 4 4 1 范围查询7 l 4 4 2k 近邻查询7 3 第五节本章小结7 5 第五章总结与展望7 7 第一节总结7 7 第二节展望7 8 参考文献7 9 致谢8 2 个人简历、在学期间发表的学术论文及研究成果8 3 v 第一章引言 第一章引言 第一节研究背景 对等( p e e r - t o p e e r ) 网络是一种采用了点对点对等计算模式的网络系统。 由于自身的优势，在过去的几年里，基于p 2 p 技术的应用在i n t e r n e t 上迅速发 展，已经成为i n t e m e t 的主要应用之一【l l 。基于p 2 p 技术下载的音频和视频文 件已经成为i n t e m e t 用户流量的主要部分1 2 1 。而基于p 2 p 原理的软件如e m u l e p j 、 e d o n k e y l 4 1 5 1 和b i t t o r r e n t 6 】等已经成为i n t e m e t 上最流行的文件共享和分发软 件。可以说p 2 p 技术正在渗透网络的每一个角落，逐渐地颠覆和取代传统网络 的结构模式。 传统c l i e n t s e r v e r ( c s ) 模式的网络随着个人计算机数量的增加，服务器的 负载加重，逐渐难以满足客户的需求。随着软硬件技术的发展，个人计算机的 性能正在逐步提升，但是在传统的c s 模式中，个人计算机只是充当客户端的 角色，这样就造成了处在网络边缘的客户端资源的闲置。网络用户对信息共享 要求的提高，以及个人计算机性能的提升，极大地推动了p 2 p 技术的发展。p 2 p 打破了传统的c s 模式，网络中每个节点的地位都是平等的，所有节点都拥有 对等的功能和责任，即每个节点既充当服务器，为其他节点提供服务，同时也 是客户机，享受其他节点提供的服务。节点之间的交互也是对等的，相互之间 可以直接进行数据的传输。 p 2 p 网络引导着i n t e m e t 架构从集中式向分布式转变，将网络应用的核心从 中心服务器向网络边缘的终端设备扩散。不论是服务器，还是普通的个人电脑， 甚至手机等移动设备，都可以参与到p 2 p 网络中来，为p 2 p 网络提供资源和服 务，同时也享受p 2 p 网络中的资源和服务。i n t e r n e t 上采用p 2 p 技术的应用层 出不穷，不过从目前的应用来看，p 2 p 最大的功能主要体现在资源和服务的共 享上。资源的共享最关键的问题之一就是如何定位资源，也就是说如何在大规 模，动态的p 2 p 网络中找到满足用户需求的资源，同时将网络通信开销，节点 计算开销，以及用户的等待时间等控制在可接受的范围之类，而这正是p 2 p 搜 索技术需要解决的问题。 第一章引言 第二节研究现状 p 2 p 网络使得i n t e m e t 上用户之间分享信息和资源变得更加方便，这也是促 进其迅速发展的重要原因之一。然而随着网络的发展，i n t e r n e t 用户迅速增加， 网络上的信息和资源呈现指数级增长的趋势。而p 2 p 网络中的资源具有极大的 分散性，同时由于p 2 p 网络中的节点频繁地加入和退出导致p 2 p 网络中的资源 一直处于不断的变化之中。如何在p 2 p 网络中准确而迅速地搜索到特定的资源 是所有p 2 p 系统面临的一个问题。 最初的无结构化p 2 p 系统( 如n a p s t e r 、g n u t e l l a ) 通常采用的是洪泛机制 来进行资源搜索，这种机制的特点是节点覆盖率高，查询成功率高，健壮性好。 但是随着p 2 p 网络规模的扩大，洪泛机制会产生大量的冗余查询消息，造成网 络的拥塞，查询的效率也非常低。 随着结构化p 2 p 的兴起，国内外的研究机构将重心转向了结构化p 2 p 网络 中资源搜索技术的研究，也取得了一定的成果。最重要的研究成果应该是基于 d h t 的结构化搜索算法。基于d h t 的p 2 p 系统【1 0 1 采用相容散列函数，根据关 键词进行精确的查找。d h t 网络中的节点共同维护一个巨大的散列表，每一个 节点都管理并维护着属于自己的那部分散列表。在d h t 网络中，网络拓扑和 节点的位置都有严格的控制，这就保证了d h t 网络的鲁棒性和可扩展性。同 时由于采用了确定的拓扑结构，d h t 可以提供精确的资源查找功能。只要目标 资源存在于网络中，d h t 总能将其搜索到，资源精确搜索的准确性得到了保证。 c h o r d 、c a n 以及p a s t r y 都是基于d h t 的p 2 p 网络的典型代表。第二章将会 对这三个系统进行简单的介绍。 然而随着网络的发展，网络中的信息不仅在数量上高速膨胀，而且形式上 也更加多元化。网络中的信息已经不再只是简单的文本或者网页，而是增加了 各种形式的信息，比如音频、视频、图片文件等等。网络用户的需求也不再停 留在只搜索精确匹配的目标，而要求对相似的目标进行搜索，比如搜索相似的 图片、视频等等。基于d h t 的p 2 p 系统如c h o r d 、c a n 等虽然很好地解决了 资源精确搜索的问题，但是却不能很好地支持相似搜索。因为d h t 在发布资 源时是通过分布式哈希函数将资源发布到对应的节点上，而为了保证负载均衡， d h t 中的散列函数总是尽量保证生成的散列值均匀随机分布，这样就导致了两 个不完全相同，但是相似度很高的资源经过散列函数生成的散列值差异很大， 2 第一章引言 结果就是资源被发布到完全随机的两个节点上。很有可能这两个节点的距离非 常远，这就给资源的相似搜索带来了困难。针对c h o r d 和c a n 在相似搜索问 题上的局限性，相关研究人员在这两个p 2 p 架构的基础上，提出来两个新的架 构，分别是m c h o r d 和m c a n 。m c h o r d 通过代表点将数据空间划分为n 个 区域，然后通过i d i s t a n c e 将这些区域映射到一维的线性空间，最后再根据c h o r d 协议对数据进行发布和搜索。m c a n 先通过代表点将原始数据空间映射到低 维向量空间( 空间维度由代表点个数确定) ，然后根据c a n 协议将该向量空间 划分给不同节点。数据的发布和搜索都在该向量空间上进行。这两个架构的基 本思想十分相似，都是通过选取代表点将原始数据空间划分成多个小的区域， p 2 p 网络中的每个节点负责其中的一块或者几块区域。这样的方式可以保证将 相似数据尽可能地发布在相同或者相近的节点上，进行相似查询时只需要查询 搜索目标附近的区域就可以得到结果。 但是注意到m c a n 和m - c h o r d 采用的方式都是将高维的数据映射到低维 空间，然后在低维空间上进行数据的发布和查询。而事实上，数据从高维到低 维的映射过程中丢失了大量的信息，所以在进行相似搜索时，低维搜索区域比 有效的区域要大很多。g h t 通过索引树的方式直接对数据进行发布和查询， 而不需要将数据从高维映射到低维，所以不存在这样的问题。进行相似搜索时， g h t * 通过对索引树进行剪枝可以将搜索的区域尽可能地减少。但是g h t * 是对 整个原始数据空间建立索引，每一个节点都必须要保存这样一份对整个数据空 间的索引树，数据规模的扩大必然会导致性能的下降。 第三节论文研究内容 本文针对当前p 2 p 网络的搜索技术的研究背景、研究现状、以及存在的问 题进行了详细的分析，主要致力于研究p 2 p 网络相似搜索中的分层索引机制。 主要工作如下： 1 ) 分析了现有p 2 p 相似搜索系统( 如m c h o r d 、m c a n 、g h t * ) 的基本 架构和原理，详细阐述了各个系统中相似搜索的关键技术，并且分析和比较了 他们的优缺点。 2 ) 分析了m c a n 和m c h o r d 在进行相似搜索时的缺点，并且针对该缺 点，提出了一种分层索引结构m c a n 。m c a n * 通过对节点在欧式空间中进 第一章引言 行d e l a u n a y 三角剖分，形成新的底层拓扑结构，并且在该拓扑结构上设计了一 种启发式的路由算法。m c a n * 中的每一个节点都负责对邻居节点建立索引。 索引分成两层：上层坐标欧式空间索引以及下层原始数据度量空间索引。其中 上层索引主要用于路由，下层索引在数据发布时帮助实现数据的聚类以及在数 据搜索时优化搜索范围。 3 ) 论文详细地阐述了m c a n * 仿真软件的设计与实现。详细介绍了基于 离散事件队列的多节点模拟的实现方法，以及仿真软件中的几个重要的模块算 法的实现，包括索引树维护模块、路由模块、数据发布模块、范围查询模块、 k 近邻查询模块、节点加入模块以及节点退出模块。 4 ) 本文利用仿真软件测试了m c a n * 的效率。在两个数据集上对m c a n * 的性能进行了测试与分析。重点比较了m c a n * 和m c a n 在进行相似搜索时 的效率。实验结果表明，m c a n * 相似搜索的效率要高于m c a n 。同时也表明 该分层索引仿真软件能较好地模拟分层索引系统的节点行为，可以作为评测 m c a n * 效率的一个很好的工具。 第四节论文结构 本文共分为五个部分，具体内容安排如下： 第一章主要介绍了p 2 p 网络，讨论了p 2 p 相似搜索的研究背景，研究现状 和存在的问题。最后说明了本文的研究目的和意义，并且简要地阐述了本文主 要的研究内容。 第二章首先介绍了p 2 p 网络的基本概念，特点及主要应用。其次介绍了两 p 2 p 相似搜索的概念，包括度量空间、范围查询以及k 近邻查询。然后介绍了 度量空间中的集中式索引结构m t r e e 和s s s t r e e 以及分布式索引m - c a n 、 m c h o r d 、g h t * 。最后分析了现有p 2 p 相似搜索架构中存在的问题，并且针对 这些问题提出了分层索引结构m c a n * ，论文详细地分析了m c a n * 的原理和 结构，并且对m c a n * 中数据的发布和搜索算法进行了详细的阐述。 第三章详细介绍了仿真软件的设计与实现。首先介绍了基于离散事件队列 的多节点模拟的实现，然后介绍了仿真软件中的几个主要模块算法的实现，包 括索引树维护模块、路由模块、数据发布模块、范围查询模块、k 近邻查询模 块、节点加入模块以及节点退出模块。 4 第四 并且比较 第五 件的特点 第二章p 2 p 相似搜索研究基础 第二章p 2 p 相似搜索研究基础 第一节p 2 p 网络综述 p 2 p 网络是一种新型的网络结构，具有传统c s 模式所不具备的优点。 随着网络技术的发展以及网络用户需求的不断升级，p 2 p 网络的应用领域将越 来越广泛，其技术也将越来越成熟。总的来说p 2 p 网络有如下几个特点： 1 ) 无中心节点：p 2 p 网络不存在中心节点，网络中的资源都分布在各个节 点上，数据的传输可以直接在节点之间进行，不需要通过服务器，这样就避免 了服务器可能带来的瓶颈。 2 ) 自适应性：节点可以自由地加入和退出p 2 p 网络，同时网络拓扑会随 着节点的加入和退出自动调整。 3 ) 可扩展性：理论上来说，p 2 p 网络中节点数量是没有限制的。因为整个 p 2 p 网络结构是全分布式的，所以节点的增多不仅不会对整个系统的性能造成 太大的影响，反而能在一定程度上提高系统的健壮性。 4 ) 健壮性：传统c s 模式的网络，一旦服务器受到攻击，那么服务便会中 断。而在p 2 p 网络中，各个节点之间相互为对方提供资源和服务，不存在中心 节点。即使部分节点因为遭到破坏而失效，p 2 p 网络也可以自动调整网络的拓 扑结构，保证服务的可用性。 除此之外，p 2 p 网络还具有容错性好、成本低等特点。这些特点使其可以 充分利用i n t e m e t 上的闲置资源，加快信息的传播速度以及优化网络带宽的使 用。同时这些特点也使得p 2 p 网络在分布式计算，文件共享以及流媒体等领域 有了广泛的应用。最近几年来，p 2 p 技术主要研究和应用的方向有如下几个： 1 ) 文件共享：节点之间可以通过p 2 p 协议直接共享文件，而无须经过服 务器中转。典型的p 2 p 文件共享系统有：n a p s t e r t 7 1 、g n u t e u a 引、k a z a a l 2 6 】、 e m u l e t 3 1 、e d o n k e y t 4 1 、m a z e 2 7 1 2 8 】等。 2 ) 分布式数据存储：p 2 p 网络可以充分利用网络中空闲的存储空间，并将 其聚合成一个大容量的存储系统。通过节点之间的协作来完成数据的存取操作。 典型的p 2 p 网路存储系统有o c e a n s t o r e l 2 9 1 、p a s t l 3 0 1 、c f s l 3 1 】、f a r s i t e l 3 2 j 等。 6 3 ) 分布式计算：p 2 p 网络可以通过节点之间的协调与合作，充分将网络中 闲置的计算资源整合到一起来完成大型的计算任务。典型的应用实例有 s e t i h o m e l 3 3 】、x e n o s e v e r s 【3 4 】等。 4 ) 网络流媒体：基于p 2 p 技术的流媒体系统通过引入应用层组播技术， 只有少数节点需要从服务器获取数据，更多的节点则通过相互之间共享数据来 获取多媒体数据流。典型的p 2 p 流媒体系统有p p l i v e t 3 5 】、p p s t r e a m 3 6 1 等。 5 ) 即时通信：现在很多即时通信软件都采用中央服务器和p 2 p 技术相结 合的方式。虽然系统中存在中央服务器，但是服务器只是用来认证用户的基本 信息，而文本传输、语音视频等都可以点对点进行，不需要经过中央服务器中 转。典型的即时通信工具有q q 3 7 1 、m s n 3 5 】、s k y p e l 3 9 1 | 删等。 以上几种只是p 2 p 技术的主要应用，p 2 p 技术在其他方面有着广泛的应 用，比如分布式搜索、协同工作等领域。由于其自身的优势和特点以及在i n t e m e t 上的广泛应用，p 2 p 技术越来越得到人们的重视。 p 2 p 网络按照其拓扑结构可以分为两大类：无结构化p 2 p ( u n s t r u c t u r e d t o p o l o g y ) 和结构化p 2 p ( s t r u c t u r e dt o p o l o g y ) 。其中无结构化p 2 p 网络根据是否 有中央服务器进行集中管理，又可以划分为集中式、分布式和混合式三种不同 模式。无结构化p 2 p 底层拓扑一般采用随机图结构，通常采用的是洪泛机制来 进行资源搜索。这种机制特点是节点覆盖率高、查询成功率高、健壮性好。但 是随着p 2 p 网络规模的扩大，洪泛机制会产生大量的冗余查询消息，造成网络 的拥塞，同时查询的效率也非常低。典型的无结构化p 2 p 网络架构为n a p s t e r t 7 j 和g n u t e l l a 8 1 1 9 1 。结构化p 2 p 中，每个节点都有通过独立的节点i d 来标识，系 统根据节点i d 将节点组织为固定的拓扑结构。在节点和加入和退出，系统都 会动态地维护该拓扑结构，并且保证该拓扑结构的正确性。在搜索资源时，特 定的路由协议可以保证搜索的效率和资源的可达性。c h o r d t l l j 、c a n t l 2 1 和 p a s t r y 1 3 】是比较具有代表性的结构化p 2 p 网络架构。 第二节相似搜索概念 给定一个数据空间，以及一个查询目标，在该数据空间中查找与目标数据 相似或者相近的数据即可以定义为相似搜索。数据之间的相似性则是通过用户 在数据空间中定义的距离函数来计算。用户可以自定义一个相似的条件，相似 7 第二章p 2 p 相似搜索研究基础 搜索的结果即为数据空间中所有满足该相似条件的数据，通常是与查询目标之 间距离小于某个值的数据集合。由于本文主要关注度量空间中的相似搜索问题， 所以下面首先介绍度量空间概念，然后介绍最常见的两种相似查询方式：范围 查询和k 近邻查询。 2 2 1 度量空间 度量空间【2 2 】【2 3 】的数学定义为：给定数据空间d ，d 为数据空间d 中的距离 函数，用于计算d 中任意两个数据之间的距离。则m = ( d ，d ) 称为度量空间。 其中度量空间m 中的距离函数d 必须满足如下条件： 1 ) 非负性：v x ，y d ，a ( x ，y ) 0 2 ) 对称性：慨，y d ，c l ( x ，y ) = a ( y ，x ) 3 ) 一致性：垤，y d ，x = y 营a ( x ，y ) = 0 4 ) 三角不等式特性：v x ，y ，z d ，c l ( x ，z ) c l ( x ，y ) + d ( y ，z ) 举例来说，如果数据空间d 定义为二维欧式空间中的所有点，距离函数d 定义为二维欧式空间中两点的直线距离计算函数。显然距离函数d 满足上面列 出的所有条件。那么m = ( d ，d ) 则组成了一个最常见的欧式度量空间。 2 2 2 范围查询 相似查询中最常见的就是范围查询，给定度量空间m = ( d ，d ) ，查询目标g ， 以及相似半径，范围查询返回度量空间中离查询目标g 小于等于，的所有数 据。其数学定义如式( 2 1 ) 所示： r ( q ，) = x d ，a ( x ，q ) ， ( 2 1 ) 如图2 1 所示，查询目标位g ，搜索半径为，则范围查询的结果为集合 0 4 、 0 5 、0 9 ) ，即所有离查询目标q 距离小于等于，的数据都包含在查询的结果中。 8 另外值得 查找，即在数 o o l o 2 2 3k 近邻查询 o 0 l o0 2 0 8 oo i l 图2 1 范围查询示意图 o 0 3 o 0 6 图2 2k 近邻查询示意图 o o l o 0 7 o 给定度量空间m = ( d ，d ) ，查询目标g ，以及查询结果数k ，k 近邻查询返 回在数据空间中距离查询目标g 最近的k 个数据对象。其数学定义如式( 2 2 ) 所示： 9 k n n ( q ， 如图2 2 所示，查询目标位g ，查询结果数k = 4 。则k 近邻查询的结果为 集合 0 4 、o s 、o s 、0 9 ，即数据空间距离查询目标g 最近的4 个数据对象。 第三节集中式索引 z 3 1m t r e e m t r e e 【2 4 1 1 4 2 】【4 3 1 是由p a o l oc i a c c i a 等人提出的一种针对度量空间的动态索引 结构。m t r e e 采用了类似于b + 树的结构进行索引，其节点分为两种，叶子节点 和中间节点。叶子节点存储数据信息，而中间节点则在数据插入和数据查询的 时候起到路由的作用。 每一个中间节点有一个自己的i dd ，、覆盖半径，( d ，) 、以及指向覆盖的子 树的指针p t r ( t ( o , ) ) 。子树r ( q ) 中存储的所有数据与节点i dd ，的距离都小于 等于节点的半径，( d ，) 。此外中间节点还维护自身与父节点的距离d ( d ，尸( d ，) ) 。 每一个中间节点维护的信息如表2 1 所示。 表2 1 中间节点需要维护的信息表 符号定义 d ， 节点的i d p t r ( t ( o , ) ) 指向子树的指针 ，( d ，) 节点覆盖的半径 d ( q ，p ( o r ) ) 节点与父节点的距离 每一个叶子节点同样需要一个节点i do j ，但是叶子节点不需要维护覆盖 半径，只需要维护一个指向数据的指针。耐( q ) 。此外同中间节点一样，每个叶 1 0 子节点也需要维护自己与父节点的距离d ( q ，p ( q ) ) 。每一个叶子节点需要维护 的信息如表2 2 所示。m t r e e 中节点维护的信息如图2 3 所示。 表2 2 叶子节点需要维护的信息表 符号定义 q 节点i d o z a ( o j ) 指向数据的指针 d ( q ，p ( q ) ) 节点与其父节点的距离 中间节点 t l 院i o i d ( o , 。) 旧( d l 。，尸( d l 。) ) n j d 耐( d l ：) l d ( 0 l ：，p ( q ：) ) i 吼j d 耐( d i 。) i d ( d l 。，e c o , 。) ) i 图2 3m - t r e e 中节点示意图 图2 4 m - t r e e 示意图 m t r e e 树中的中间节点将数据空间划分成不同的区域，每一个中间节点负 责一部分区域，其区域中所有数据离节点i d 的距离都小于等于节点的覆盖半 径。图2 4 为文献 2 1 1 中给出的m - t r e e 示意图。 1 ) 范围查询 进行范围查询时，从根节点开始往下递归遍历m t r e e 树的子树，在遍历时， 可以通过三角不等式关系对m t r e e 树进行剪枝，从而可以跳过部分不包含目标 数据的子树。提高搜索的效率。范围查询搜索的伪代码如下： r s ( n ：n o d e ，q ：q u e r y _ o b j e c t ，r ( q ) ：s e a r c h r a d i u s ) l e tq b et h ep a r e mn o d eo f n o d en ； i f ni sn o tal e a f n o d e t h e n vd ，i nn d o ： i f ld ( q ，q ) 一d ( 0 ，q ) i s ，( q ) + ，( d ，) t h e n c o m p u t ed ( d ，； i fd ( d ，9 ，( q ) + ，( d ，) t h e n r s ( p t r ( r ( o r ) ) ，q ，( q ) ) ；) ) e l s e vqi nn d o ： i f ld ( o _ ，q ) 一d ( g ，q ) i ，( q ) t h e n c o m p u t e rd ( q ，q ) i f d ( q ，9 ) ，( 9 t h e na d dd 谢( q ) t