（计算机软件与理论专业论文）利用分区和距离实现chord中高维数据范围检索.pdf

大连理工大学硕士学位论文 摘要 近年来随着p 2 p 系统的大量出现，p 2 p 技术逐渐成为人们研究的热点。p 2 p 技术目 前主要应用在资源共享、分布式计算、协作系统、电子商务和以p 2 p 为基础的深度搜索 引擎等方面。其中，信息检索是最常见的一种应用，对现有的图像、视频等高维数据内 容的检索更是迫切的需求。 在p 2 p 共享系统中，每个节点既可以将本地资源共享出来与其它节点分享，又可以 从其它节点获取资源，实现了服务器与客户端的两位一体。然而，现有的信息检索机制 存在着种种不足：基于结构化p 2 p 网络的检索效率很高，但是由于构造过于严格，难以 实现模糊、范围、肛近邻等复杂查询，仅支持精确的单关键字查询；非结构化p 2 p 网络 实现简单，但是由于搜索的盲目性，其检索效率普遍比较低。 本文在深入研究p 2 p 信息检索技术的基础上，重点研究了基于结构化p 2 p 网络的信 息检索技术和高维数据的索引算法。现有的结构化p 2 p 网络对范围检索等复杂查询缺乏 有效的支持；单一的使用降维或近似向量对高维数据进行索引查询，索引时会损失高维 数据的大量信息，查询时会引入大量的误中点。以c h o r d 网络为基础，针对i d i s t a n c e 索引进行范围查询时引入大量误中点的问题，论文提出了一种基于分区和距离的高维数 据索引方法。首先采用c o d e d i s t a n c e 索引技术对高维数据建立一维索引值，并利用位 置保持哈希函数为每个索引值赋予一个唯一的标识，然后将该标识保存在c h o r d 环节点 上，生成b m c h o r d 系统。在此基础上，给出了数据过滤策略和范围查询算法。最后用 实验结果验证了b m c h o r d 系统在减少查询的误中点个数、提高查准率等方面的有效性。 关键词：范围检索；c h o r d ；i d i s t a n c e ；区位码；位置保持哈希函数 利用分区和距离实现c h o r d 中高维数据范围检索 r a n g eq u e r yo fh i g h d i m e n s i o n a ld a t ao nc h o r db a s e d o n b i t c o d ea n dd i s t a n c e a b s t r a c t i nr e c e n ty e a r s ，a l o n gw i t ht h ee m e r g e n c eo fm a n yp 2 ps y s t e m s ，t h ep 2 pt e c h n i q u eh a s b e e nt h eh o t s p o tt os t u d y ，n o wt h ep 2 pt e c l - m i q u ei sm a i n l ya p n i e di nf i l e s b a r i n g ，d i s t r i b u l e d c a l c u l a t i o n ，c o o p e r a t i n gs y s t e m s ，e l e c t r o n i cc o m m e r c ea n ds e a r q he n g i n e t h ei n f o r m a t i o n r e t r i e v a li so n eo ft h em o s tp o p u l a rp 2 pa p p l i c a t i o n i ti st h eu r g e n tn e e d st or e t r i e v e h i g h d i m e n s i o n a ld a t ao fp i c t u r ea n dv i d e o ap 2 p f i l e s h a r i n gs y s t e m e a c hp e e rp e r f o r m sa sb o t hs e y v e ra n dc l i e n ! ，w h i c hr e c a l l s t h a tt h e yg e tr e s o u r c e s 内r mo t h e rp e e r aa n dp r o v i d er e s o u r c e s 白ro t h e rp e e r sa tt h es a m et i m e ， h o w e v e r ，t h e r ea r em a n yw e a kp o i n t si ne x i s t i n gp 2 pr e t r i e v a lm e c h a n i s m s f o re x a m p l e ，t h e r e t r i c x ，a li ns t r u c t u r e dp 2 ps y s t e m si se f f i c i e n tb u tl a c ko fs u p p o r tt os i m i l a r i t yr e t r i e v a l b e c a u s eo ft h e i rc o m p l i c a t e ds t r u c t u r e s a n di ! ( j i l l o n l ys u p p o r ta c c u r a t es i n g l ek e y w o r d q u e r i e s e v e nt h o u g hu n 3 t r u c t u r e dp 2 ps y s t e m sc a bb ei m p l e m e n t e ds i m p l ya n dm o r ep o p u l a r ， t h e ya r ei n e f 矗c i e n tb e c a u s eo ft h eb l i n d n e s sd u r i n gt h ei n f o r m a t i o nr e t r i e v a l b a s e do ni n t e n s i v es t u d yo fi n f o l r m a t i o nr e t r i e v a li np 2 pe n v i r o n m e n t t h i sp a p e r e m p h a t i c a l l ys t u d yt h ei n f o r m a t i o nr e t r i e v a lt e c h n o l o g yj ns t r u c l u r a lp 2 pn e l w o r ka n dt b f i n d e xa l g o r i t h mo fh i g hd i m e n s i o n a ld a t a t h er a n g eq u e r yo fh i g h d i m e n s i o n a li ns t r u c t u r e d p 2 pn e t w o r ki si n e f f i c i e n to w i n gt ol a c ko fs u p p o r tw i t hs i m i l a r i t ys e a r c h ；m a n yf a l s eh i t sa n d l o r so fi n f o r m a t i o nl o s tw e r ec a u s e dw h e nu s ed i m e n s i o n a l i t yr e d u c t i o nm e t h o d so r a p p z o xl 1 1 a 【ev e c t o rt e c h n o l o g yt nh i g h - d i m e n g i o n a td a t ar e l r i e v a l ，i no , d e zt ot a c k l et h e p r o b l e mt h a tt h e r ea t el o t so ff a l s eh i t si nr a n g eq u e r yu s i n gi d i a t a n c ei n d e xt e c h n o l o g y ，a h i g h d i m e n s i o n a ld a t ai n d e xa l g o r i t h mb a s e do nb i t c o d ea n dd i s t a n c ei sp r o p o s e di nc h o r d s y s t e mc o d e - d i s t a n c et e c h n o l o g ya n dl o c a l i t y - p r e s e r v i n gh a s h i n gf u n c t i o nw e r ea d o p t e dt o e s t a b l i s hi d i m e n s i o n a li n d e xv a l u e sa n di d e m i 0e v e r yi n d e ，( w 】l bau n i q u em a r kr e s p e c t i v e l y t h e nt h eb m c h o r ds y a t e mi sc o n s t c t e db ys t o r i n gt h em a r k si n t oc h o r dn o d e 3 i na d d i t i o n ， ad a t af i l t e r i n gs t r a t e g ya n dr a n g eq u e r ya l g o r i t h ma r eg i v e no nt h a tb a s i s e x p e r i m e n t a l r e s u l t ss h o wt h a tb m ，c h o r ds y s t e mh a sa d v a n t a g e so v e rr e d u c i n gt h es e t go fi n t e r m e d i a t e r e s ui ta n d i m p r o v i n gr e c a l lr a t i o k e yw o r d s ：r a n g eq u e r y ；c h o r d ；i d i s t a n c e ；b i t c o d e ；l o c a i i t y p r e s e r v i n g h a s h in 9f u n c t i o n i i 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 作者签名：尘丝擞日期：也2 年厶月三日 导师签名：锱缸日期：- 咩年l 月望日 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 1绪论 1 1p 2 p 网络技术 1 1 1p 2 p 网络研究的意义 p 2 p ( p e e r - t o p e e r ) 即对等计算或对等网络，简单的定义成通过直接交换来共享计算 机资源和服务的网络。在p 2 p 网络环境中，成千上万台彼此连接的计算机处于对等地位， 整个网络不依赖于专用的集中服务器。网络中每台计算机既能充当网络服务的请求者， 又能对其他计算机的请求做出响应，提供资源和服务。提供的资源和服务可以包括：信 息共享和交换、计算资源( 如c p u 共享) 、存储资源( 如缓存和磁盘空间的使用) 等。 p 2 p 在网络兴起的初期就有应用。随着网络的发展和个人电脑的普及，近年来这种 技术在应用上得到了很快的发展。 人们对p 2 p 的关注，始于2 0 0 1 年关于n a p s t e r 的一场官司，结果虽然以发布p 2 p 软件的n a p s t e r 网站败诉，但是它让整个关注此项技术的人们认识到了p 2 p 技术的威力。 在此以后，各种p 2 p 概念的应用软件和服务不断被推出。其中不但有个人编写的应用软 件，而且还有一些i t 巨头在p 2 p 领域投入大量资源进行研究和开发，微软发布了 w i n d o w sx pp 2 p 软件开发包，s u n 公司投入大量资源开发j x t a 平台，许多厂商也纷纷 推出自己的p 2 p 软件，众多学术团体也在致力于p 2 p 技术的研究。 基于p 2 p 的应用一个重要特点就是使人们更多的、更主动地参与到网络活动中，这 也是它能够在近几年迅速发展的原因之一。它倡导各个实体的主动性，既请求得到服务， 同时又提供服务。每一个节点都处于同等的地位，将传统的“内容位于中心 存储模式 转变为“内容位于边缘 模式【1 】。这也使得人们在i n t e m e t 上的共享行为提高到一个更 高的层次。对于p 2 p 的专门研究虽然近几年才得到重视，但是发展迅速，新技术新应用 不断涌现。 虽然以p 2 p 为指导思想的各类应用软件及各项研究在近年来取得了很多成果，但是 这种网络体系并未像最初人们乐观估计的那样对传统c s ( 客户端服务器) 体系造成重 大冲击，而只是在某些应用领域作为c s 结构的补充存在着。人们接触到最多的是基于 p 2 p 技术的聊天工具、网络游戏和文件共享等一些软件。各大公司纷纷推出自己的p 2 p 体系架构，互不兼容。这里最主要的原因就在于p 2 p 本身的网络特征、社会应用的需求 以及技术的局限性。p 2 p 强调个体参与，但是由于参与者的层次参差不等，使得应用只 能局限在小范围的节点中，或是特殊的应用中( 如聊天工具和文件下载) 。另外，也可 以看到，p 2 p 的发展是和网络的普及分不开的，并随着人们需求的日益多元化，p 2 p 的 利用分区和距离实现c h o r d 中高维数据范围检索 功能也在不断改进和完善。随着p 2 p 技术的不断发展，应用环境的不断丰富，它在各个 层面的应用会逐步完善。 p 2 p 网络技术将成为引领互联网进入下波发展大潮的主线，由于p 2 p 网络巨大的 前景，世界上一些主要的国家和主要的公司在p 2 p 网络基础设施的建设和p 2 p 网络平台 的开发和应用上加大了投资力度。p 2 p 网络是未来i n t e r n e t 的发展方向，也就是说，p 2 p 网络会成为未来的网络基础设旌，其应用领域将是十分宽广的。 1 1 2p 2 p 网络特点 与其他网络模型相比，p 2 p 网络具有以下几个特点： ( 1 ) 分散化 网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直接在节点之 间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。即使是在混合p 2 p 中， 虽然在查找资源、定位服务或安全检验等环节需要集中式服务器的参与，但主要的信息 交换最终仍然在节点中间直接完成。这样就大大降低了对集中式服务器的资源和性能的 要求。分散化是p 2 p 的基本特点，由此带来了其在可扩展性、健壮性等方面的优势。 ( 2 ) 可扩展性 在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务 能力也在同步地扩充，始终能较容易地满足用户的需要。即使在诸如n a p s t e r 等混合型 架构中，由于大部分处理直接在节点之间进行，大大减少了对服务器的依赖，因而能够 方便地扩展到数百万个以上的用户。而对于纯p 2 p 来说，整个体系是完全分布的，不存 在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 3 ) 健壮性 在互联网上随时可能出现异常现象，网络中断、网络拥塞、节点失效等各种异常事 件都会给系统的稳定性和服务持续性带来影响。而p 2 p 架构则天生具有耐攻击、高容错 的优点。由于服务是分散在各个节点之间进行的，部分节点或网络遭到破坏对其它部分 影响很小。而且p 2 p 模型一般在部分节点失效时能够自动调整整体拓扑，保持其它节点 的连通性。事实上，p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地 加入和离开。一些p 2 p 模型还能够根据网络带宽、节点数、负载等变化不断地做自适应 式的调整。 ( 4 】隐私性 随着互联网的普及和计算存储能力飞速增长，收集隐私信息正在变得越来越容易。 隐私的保护作为网络安全性的一个方面越来越被大家所关注。在p 2 p 网络中，由于信息 的传输分散在各个节点之间进行而无需经过某个集中环节，用户的隐私信息被窃听和泄 大连理工大学硕士学位论文 漏的可能性大大缩小。此外，目前解决i n t e m e t 隐私问题主要采用中继转发技术，从而 将通信的参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一 机制依赖于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 ( 5 ) 高性能 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人计算机的 计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。而在目前的互联网上，这 些普通用户拥有的节点只是以客户机的方式连接到网络中，仅仅作为信息和服务的消费 者，游离于互联网的边缘。对于这些边际节点的能力来说，存在极大的浪费。采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资料分布到所有 节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。这 与当前高性能计算机中普遍采用的分布式计算的思想是一致的。但通过利用网络中的大 量空闲资源，可以用更低的成本提供更高的计算和存储能力。 1 。1 3p 2 p 网络结构 p 2 p 系统的最大特点就是各节点之间直接共享资源，其核心技术就是分布式对象的 定位机制，p 2 p 网络的体系结构直接影响着网络的性能。目前，根据p 2 p 网络的发展， 可以将p 2 p 网络划分为：集中式p 2 p 模型、非结构化p 2 p 模型、混合式p 2 p 模型、结 构化p 2 p 模型。 ( 1 ) 集中式p 2 p 网络 在集中式p 2 p 网络中，有中心服务器，但与c s 模式不同。中心服务器只保存共享 资源的目录信息，实际的数据保存在提供这些资源的各个对等节点上。各节点之间可以 直接建立连接，但需要中心服务器提供必要的网络服务，如保存元信息、提供索引或路 由、提供安全检验等，通过集中认证，建立索引机制。服务器在此只起到辅助连接的作 用，一旦连接成功，服务器不再起作用，对等节点之间直接进行通信。与c s 模式中的 服务器相比，也可以认为是弱化了服务器的作用。在集中式p 2 p 模型中，由于服务器只 处理对等节点间的搜索请求，实际的数据存储在对等节点上，数据的交换在对等节点之 间直接进行，而不用通过中心服务器，因此大大减轻了服务器的负担，并且使各对等节 点的存储和计算能力得到了充分利用。另外，在这种模型中，由于有中心服务器为用户 提供共享和搜索服务，提高了共享资源的搜索效率。但同时要求集中式p 2 p 网络的中心 服务器能连续工作，能处理大量的用户请求，一旦中心服务器失效，整个p 2 p 网络即陷 于瘫痪。集中式p 2 p 模型的典型代表是n a p s t e r 。模型如图1 1 所示。 利用分区和距离实现c h o r d 中高维数据范围检索 图i i 集中式p 2 p 框架结构 f i g 1 1 c e n t r a l i z e dp 2 pn e t w o r ks t r u c t u r e 查询流 下载流 ( 2 ) 非结构化p 2 p 网络 在非结构化p 2 p 网络中，不存在中心服务器，链状的节点之间构成一分散式网络。 网络中的各节点都是对等的，具有相同的能力。任何一个单独的、任意的终端实体离开 网络，都不会给网络中的服务带来大的损失。通过基于对等网络协议的客户端软件搜索 网络中存在的对等节点，节点之间不必通过服务器，可直接建立连接。搜索时，对等点 向其相邻节点发出请求，若其相邻节点没有所要资源，则转发相应请求，直到发现资源， 再与拥有此资源的节点建立连接并交换数据。非结构化p 2 p 模型由于没有中心节点，不 存在中心节点失效的问题。但由于其搜索和发现是通过向直接相连的节点查询或广播得 到，搜索请求在网络中传播范围过大，占用大量的带宽，搜索效率相对较低。非结构化 p 2 p 模型的典型代表是g n u t e l l a 、f r e e n e t 等。模型如图1 2 所示。 查询流 下载流 图1 2g n u t e l l a 的查询流程 f i g 1 2 g n u t e l l aq u e r yp r o c e s s ( 3 ) 混合式p 2 p 网络 在混合式p 2 p 模型中，结合集中式p 2 p 快速查找和纯分布式p 2 p 去中心化的优点， 大连理工大学硕士学位论文 将用户节点按能力进行分类，分为：普通节点、搜索节点和索引节点，使某些节点担任 搜索和索引等特殊任务。这种模型的关键是引入了索引节点和搜索节点等超级节点。索 引节点用来维护可用的搜索节点信息列表，处理来自其它节点的查询请求。要求索引节 点具有较大的内存以及较快的连接速度。搜索节点管理着大量用户节点以及用户节点共 享的文件列表，功能类似于集中模型中的中心服务器。搜索节点用于处理用户的搜索请 求，并从其子节点( 普通节点) 的共享文件列表中搜索。要求搜索节点具有较大的网络带 宽以及较强的处理能力。用户节点通过索引节点获得搜索节点信息，之后用户节点就与 获得的搜索节点相连，每一次查询都通过该搜索节点进行。混合式p 2 p 模型的典型代表 是k a z a a 、b t 等。模型如图1 3 所示。 图1 3 混合式p 2 p 网络结构查询流程 f i g 1 3 m i x e dp 2 pn e t w o r kq u e r yp r o c e s s 一 查询流 + 一下载流 ( 4 ) 结构化p 2 p 网络 结构化p 2 p 网络也是完全分布式的p 2 p 网络系统，通常采用的是分布式哈希表 ( d i s t r i b u t e dh a s ht a b l e 或d h t ) 的结构，所以结构化p 2 p 也叫作d h t 网络。和非结构 化p 2 p 网络相比，结构化p 2 p 网络对文档在系统中的存放位置有严格的控制并且节点之 间的关系比较紧凑。结构化p 2 p 网络的最大优点在于它可以在o ( 1 0 9 n ) ( 其中刀是系统 中节点的数目) 的跳数之内完成文档的路由和定位。结构化p 2 p 网络的主要特点是自组 织、可扩展、负载均衡以及较好的容错性。和非结构化p 2 p 网络主要用于文件共享领域 不同，结构化对等网络的这些优良特性使得它可以应用在对可靠性和扩展性要求比较高 的场合。 简单的理解，结构化p 2 p 网络中每个文档对应一个m 比特长的唯一标识符，可以 将文档的这个唯一标识符理解为一个虚拟空间中的地址。整个虚拟空间被划分为很多个 利用分区和距离实现c h o r d 中高维数据范围检索 区域，每个区域包含了若干连续的虚拟地址，系统中的每个节点负责这些区域中的个 或多个。文档被存储在负责它的虚拟地址所在区域的节点中，对文档的插入和查找操作 的路由通过文档的虚拟地址进行。虚拟空间中区域的划分和负责每个区域节点的选择都 是动态的，每次节点加入或者离开系统都会导致动态的调整。文档的唯一标识符通过对 文档内容或u r l 进行哈希变换得到，一致性哈希变换( c o n s i s t e n th a s h i n g ) 【2 j 是最常用的 算法。一致性哈希变换的特性是可以将变换后得到的m 比特长的文档标识符均匀分布在 一个值空间中，不同文档产生相同哈希值的概率几乎为零。通过对节点的i p 地址进行 相同的哈希变换得到唯一的节点标识符，并将节点标识符也映射在同一个值空间中，可 以将文档存储在有着和文档标识符最接近的节点标识符的节点那里。 结构化p 2 p 网络中主要提供两种操作：文档的插入和文档的查找。这两个操作都是 通过文档的唯一标识符进行的。系统中每个节点在路由表中保存和其相邻的节点的信 息，并比较收到的文档标识符和路由表中的节点标识符，通过选择数值上和文档标识符 最接近的节点标识符对应的节点完成文档的路由。 查询流 下载流 1 2 i d ：0 1 8 图1 4c h o r d 网络查询流程 f i g 1 4 c h o r dn e t w o r kq u e r yp r o c e s s 结构化p 2 p 网络中基于文档标识符的路由方式如图1 4 所示。图中节点1 发出对文 档标识符为0 0 0 8 0 0 的文档的查找请求，通过和它两个相邻节点2 和5 的标识符进行比 较，节点1 发现节点2 的节点标识符和其所请求文档的文档标识符更接近，于是节点1 将查找请求转发给节点2 ；通过类似步骤，这个查找请求经过了节点3 和4 ，最终到达 节点4 ：节点4 的标识符最接近所请求的文档标识符，因此该文档保存在节点4 那里， 当针对该文档的查找请求到达节点4 时，节点4 向查找发起节点1 返回所请求的文档。 大连理工大学硕士学位论文 采用了分布式哈希表结构的结构化p 2 p 网络很好的解决了系统的扩展性问题，比非 结构化p 2 p 网络更适合大规模的应用。但结构化p 2 p 网络中文档的插入和查找都是通过 文档的唯一标识符进行的，不能直接提供非结构化p 2 p 网络中常用的多关键字搜索功 能。 1 1 4p 2 p 网络技术的应用 ( 1 ) 对等计算 采用p 2 p 技术的对等计算，是把网络中的众多计算机暂时不用的计算能力连接起 来，使用累积的能力执行超级计算机的任务。需要大量数据处理的行业都可以从对等计 算中获利，如天气预报、基因的研究等，有了对等计算后，就不需要价格昂贵的计算机 了。在硅谷现在有很多公司正在投入对等计算的开发，如p o p u l a rp o w e r ，c a n t a t a 等， 并获得了巨大的风险资金。i n t e l 也利用对等计算技术来设计其c p u ，并为其节省极大的 费用，同时对等计算的发展是以p c 机资源的有效利用为根本出发点的，因此也受到了 i n t e l 的极力推崇。从本质而言，对等计算就是网络上的c p u 资源共享。 ( 2 ) 协同工作 公司机构的日益分散，使得为员工和客户提供轻松、方便的消息和写作的工具变得 日益重要。网络的出现，使协同工作成为可能。但传统的w e b 实现方式，给服务器带 来了极大的负担，造成了昂贵的成本支出。p 2 p 技术的出现，使得因特网上任意两台p c 都可以建立实时的联系，建立了这样一个安全、共享的虚拟空间，人们可以进行各种各 样的活动，这些活动可以是同时进行的，也可以交互进行。p 2 p 技术可以帮助企业和关 键客户，以及合作伙伴之间建立起一种安全的网上工作联系方式，因此基于p 2 p 技术的 协同工作也受到了极大的重视。l o t u s 公司创始人奥奇获得了6 0 0 0 万美元的风险投资， 来开发其协同工作产品g r o o v e 。 ( 3 ) 搜索引擎 p 2 p 技术的另一个优势是开发出强大的搜索工具。p 2 p 技术使用户能够深度搜索文 档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿主设备的限制， 可以达到传统目录式搜索引擎器( 只能搜索到2 0 - - 3 0 的网络资源) 无可比拟的深度 ( 理论上将包括网络上所有开放的信息资源) 。以p 2 p 技术发展的另一先锋g n u t e l l a 进行 的搜索为例：一台p c 上的g n u t e l l a 软件可以将用户的搜索请求同时发给网络上另外1 0 台p c ，如果搜索请求未得到满足，这1 0 台p c 中的每一台都会把该搜索请求转发给另 外的1 0 台p c ，这样搜索的范围将在几秒钟内以几何级数增长，几分钟内就可以搜遍几 百万台p c 上的信息资源。可以说，p 2 p 为因特网的信息搜索提供了全新的解决之道， 著名的搜索引擎公司g o o g l e 也宣称要采用p 2 p 技术来改进其搜索引擎，一家名为 利用分区和距离实现c h o r d 中高维数据范围检索 i n f r a s e a r c h 的新建公司也因为开发p 2 p 技术的搜索引擎而获得了一笔巨额风险投资。 ( 4 ) 文件共享 p 2 p 技术使在因特网上的任意两台计算机之间直接共享文档、多媒体和其他文件成 为了可能。利用p 2 p 技术，网上计算机之间可以进行直接交互，而不需要使用任何台 中央服务器。可以说，对文件交换的需求直接引发了p 2 p 技术热潮。在传统的w e b 方 式中，要实现文件交换需要服务器的大力参与，通过将文件上传到某个特定的网站，用 户再到某个网站搜索需要的文件，然后下载，这种方式对用户而言非常不方便。n a p s t e r 就是抓住了人们对m p 3 的音乐需求，其m p 3 交换直接引发了网络的p 2 p 技术革命。在 p 2 p 网络中，对等机通过不同的查询机制定位含有所需资源的其他对等机后，将直接与 其建立连接，并下载所需文件。 1 2 d h t 算法 分布式哈希表是p 2 p 网络中节点组织的一种非常有效的方式，在本文提出的 b m c h o r d 系统就借鉴了这种思想来对系统中节点进行组织管理。 d h t 实际上是一个由广域范围大量节点共同维护的巨大散列表。散列表被分割成 不连续的块，每个节点被分配一个属于自己的散列块，并成为这个散列块的管理者。d h t 算法能够为p z p 网络提供有效的搜索与路由机制。在d h t 算法中，系统中的每个节点 所拥有的资源都会根据h a s h 算法映射到一个码空间( k e ys p a c e ) ，而每个节点都会保存 一定范围的码空间及一个以k e y 值为索引的路由表。当有节点在网络中进行数据搜索时， 只需将所搜索的数据通过h a s h 函数进行码空间的映射得到k e y 值，然后在路由表中进 行路由。通过这个路由表，系统保证了从任意节点出发，查找任意数据，仅须经历有限 的节点数。简单来说，就是网络节点按照一定的方式分配到一个唯一节点标识符( n o d e i d ) ，资源对象通过散列运算产生一个唯一的资源标识符( o b j e c ti d ) ，且该资源将存储 在节点i d 与之相等或者相近的节点上。需要查找该资源时，采用同样的方法可定位到 存储该资源的节点。 d h t 结构有着良好的可扩展性、健壮性和自组织能力【3 1 。由于重叠网络采用了确定 性拓扑结构，d h t 可以提供精确的发现。只要目的节点存在于网络中d h t 总能发现它， 发现的准确性也得到了保证。 目前比较成熟的d h t 算法有t a p e s t r y 4 1 、p a s t r y t 5 1 、c a n 1 】和c h o r d f 6 l 等等。本文采 用c h o r d 算法。 大连理工大学硕士学位论文 1 3 研究课题的提出 1 3 1p 2 p 环境下的信息检索现状 p 2 p 信息检索技术是在一个分布式的网络中进行共享信息的查找与检索，这种技术 可以充分发掘p 2 p 技术的潜在优势，克服传统信息检索存在的可伸缩瓶颈等局限性。但 由于p 2 p 网络中大量的节点会随时动态地加入和退出，并且各个节点之间都是对等存在 的，因此p 2 p 网络信息检索技术比传统的检索技术要复杂，也使得它面临许多挑战。 传统的信息检索技术通常是指搜索引擎技术，搜索引擎以一定的策略在互联网中搜 集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起 到信息导航的作用。 在p 2 p 网络中，用户共享所有用户硬盘上的文件、目录，搜索无需通过w e b 服务 器，也可以不受信息文档格式和宿主设备的限制，可达到传统搜索引擎无可比拟的深度。 p 2 p 网络搜索技术主要分为4 类： ( 1 ) 集中式p 2 p 网络 集中式p 2 p 网络通过一个中心服务器来记录共享信息以及回答这些信息的查询。每 一个对等实体负责共享它的信息，下载它所需要的存储在其它对等实体上的信息。这种 形式具有中心化的特点，但它不同于传统意义上的c l i e n t s e r v e r 模式。所有的信息都分 别存放在提供该信息的客户机上，服务器上只保留索引信息，此外服务器与对等实体以 及对等实体之间都具有交互能力。如n a p s t e r 和e m u l e 。 ( 2 ) 非结构化分布式p 2 p 网络 非结构化分布式p 2 p 网络是一种纯p 2 p 网络。这种网络不需要有中心服务器和中心 路由器，其中每一个节点( p e e r ) 都作为对等实体，地位是完全平等的。每一个p e e r 既 可以作为客户机又可以作为服务器，并且它们与相邻的p e e r 有相同的能力。每个节点都 拥有自己的邻居( p e e r - g r o u p ) 。查询文件时，节点向自己所有的邻居发送查询数据包。 每一个收到查询数据包的节点将检查在自己本地存储的文件是否满足查询要求。如果满 足的话，该节点发送一个查询响应数据包给查询的发起者，节点间直接交换文件。不管 满足与否，该用户都继续将查询数据包向自己的邻居节点转发。依此类推，查询消息像 洪水一样在网络中流动。 ( 3 ) 结构化分布式p 2 p 网络 结构化分布式p 2 p 网络和非结构化分布式p 2 p 网络一样，也是一种纯p 2 p 网络， 只是在网络拓扑结构上有所不同。这类网络中每一个节点被分配一个标识符，同时用一 个关键字来表示其可提供的共享内容。网络中每个节点分别存储自己的标识符路由表进 利用分区和距离实现c h o r d 中高维数据范围检索 行路由。关键字存储在与关键字匹配的标识符节点上。进行资源定位的时候，可以通过 标识符路由表快速查询到存储关键字的节点，从而获得共享内容的存储位置。如c h o r d 、 p a s t r y 、c a n 以及t a p e s t r y 等。 ( 4 ) 混合式p 2 p 网络 混合式p 2 p 网络是集中式p 2 p 网络和分布式p 2 p 网络的集合。由于集中式p 2 p 网 络有利于网络资源的快速检索，以及只要服务器能力足够强大就可以无限扩展，但是其 中心化的模式容易遭到直接攻击；分布式p 2 p 网络解决了抗攻击闯题，但是缺乏搜索效 率以及可扩展性。混合式p 2 p 网络在分布式网络的基础上，将节点按能力进行分类，使 某些节点可以承担特殊的任务，这些节点称为超级节点。超级节点分担了网络中大部分 的检索、路由和扩展功能，使普通节点的负载下降，如s k y p e 等。 1 3 2 课题提出 在结构化p 2 p 网络中，每个节点都有固定的地址，整个网络具有相对稳定而规则的 拓扑结构。依赖拓扑结构可以给网络的每一个节点指定一个逻辑地址( 标识符) ，并把 地址和节点的位置对应起来。对于给定的某个地址，拓扑网络保证只需要通过o ( 1 0 9 ( 玎) ) 跳就能路由到具有相应地址的节点上去( 玎是网络中的节点数) 。在实际的系统中，p 2 p 网络的逻辑地址通常是由h a s h 函数得到的，每个节点都将保存一张d h t 进行路由。 给定存储信息的索引，通过d h t 能够高效率地定位到对应该索引的信息。但是d h t 网络采用散列函数将数据对象映射的毫无规律，从而对于范围、模糊、近邻等复杂查询 缺乏有效的支持。 传统的高维数据索引方法在范围查询时，引入了大量的误中点，影响了检索的效率， 如何有效的减少范围查询的误中点数据是本文研究的重点之一。 1 4 论文的主要工作 论文主要包括以下工作： ( 1 ) 介绍了p 2 p 网络的特点和结构，以及p 2 p 网络技术的应用。 ( 2 ) 介绍了p 2 p 环境下的信息检索现状，提出了本文研究的课题。 ( 3 ) 分析了p 2 p 环境下范围检索的特点和现状：为了应对大量高维数据分布的不 均匀性，本文研究了聚类划分策略。 ( 4 ) 作为结构化p 2 p 的c h o r d 网络，结构过于严格、分布式散列表又将数据对象 映射的毫无规律，使得c h o r d 网络对于范围检索等复杂查询缺乏有效的支持。以前的基 于c h o r d 的范围检索算法虽然在查准率上达到了较好的效果，但是查询的中间结果数据 量太大，引入了大量的误中点数据，增加了精简查询的代价，降低了查询的效率。本文 大连理工大学硕士学位论文 提出了基于分区和距离的c h o r d 高维数据范围检索系统b m c h o r d ，充分利用近似向量 和一维转换两种高维数据索引技术，在保证查准率的条件下，有效的减少了查询误中点 的个数，提高了查询的效率。 1 5 论文的组织结构 在第一章中，主要叙述p 2 p 网络的研究意义，p 2 p 网络特点及结构，并介绍了p 2 p 环境下的信息检索现状。 第二章，深入分析了高维数据范围检索的特点、目标以及p 2 p 环境下高维数据范围 检索研究现状。 第三章，提出了基于分区与距离的c h o r d 环高维范围检索系统。 第四章，用大量的实验验证了b m c h o r d 在减少误中点数目、提高检索效率方面的 有效性，并对实验结果进行了分析。 利用分区和距离实现c h o r d 中高维数据范围检索 2p 2 p 高维范围检索技术 2 1 对等计算系统中的查询处理 2 1 1 主题查询处理 现有的非结构化p 2 p 系统主要采用了基于洪泛的查询扩散、随机选择搜索路径、集 中式目录索引等资源定位技术。这些方法的搜索效率低下，浪费了系统中的各种资源， 而且限制了系统的可扩展性。如何能够只查询部分数据，就能够取得比较好的甚至超过 查询全部数据得到的查询结果，这就是分布式主题查询处理需要解决的问题之一。 为了解决上述问题，c r e s p o 等人提出了一种基于主题的路由索引( r o u t i n gi n d e x ) 7 1 ， 解决了非结构化p 2 p 系统中的信息搜索问题。从本质上说，路由索引是一种基于主题的 信息统计技术。在该方法中，每个节点都维护了一张路由表，每个路由表项都记录了邻 居节点上包含的某个主题的文档个数。在路由主题查询时，根据本地的统计信息，每个 节点都可以选择包含与查询主题相关的最多文档数目的邻居节点，并将主题查询发送给 这些邻居节点。为了建立并维护路由索引，每个节点都需要将自己所了解的统计信息广 播给所有邻居节点。根据这些新的统计信息，每个邻居节点在更新了本地的路由索引信 息之后，继续将更新后的统计信息发送给它的邻居节点，依次类推。然而，在非结构化 p 2 p 系统中，节点可以随意地加入或退出系统。这将导致系统中的大量更新操作。此外， 系统只能支持形式简单的主题查询，无法支持层次型的主题结构。因此，这种路由索引 对实际应用局限性较大。 2 1 2 关系查询处理 对等计算系统中的关系查询处理又可以分为以下几种类型悼j ： ( 1 ) 基于d h t 的查询处理 文献【9 】首先提出了基于d h t 的查询处理，其基本思想是；通过d h t 将数据对象与 查询映射到同一个标识符空间，从而实现查询处理。 ( 2 ) 基于中介的查询处理 p i a z z a 1 0 】利用信息集成系统中基于g a v 和l a v 的查询重写技术【1 ，实现了无结 构化p 2 p 环境下的查询处理。p i a z z a 利用中介( m e d i a t i o n ) 和信息提取( i n f o r m a t i o n e x t r a c t i o n ) 技术，来描述每个节点的本地存储模式，并在不同节点上的存储模式之间建 立起映射关系。当用户发出查询q ，q 将被重写为两个新的查询9 和q ”。q 是针对本 地存储模式的重写查询；而q “是针对邻居节点的存储模式的重写查询。这样，查询请 求节点在本地执行查询q ，而查询q ”则被发送给邻居节点。接收到查询o ”的邻居节 大连理工大学硕士学位论文 点将继续执行上述操作，并将新的重写查询发送给它的邻居节点，依此类推。本地结点 和其它节点返回的结果的并集被作为最后结果返回给用户。 ( 3 ) 基于代理技术的查询处理 每个节点都有一个本地字典和一个导出字典，存放了该节点的本地存储模式和共享 给其它节点的模式信息，每个节点都使用代理来发送和执行用户查询。 ( 4 ) 突变查询处理 一个突变查询处理计划是一个使用统一资源标识符作为资源描述的x m l 查询树。 一个突变查询计划将顺序地遍历网络中的节点。为了有效地路由突变查询计划，系统提 供了一种分布式的目录索引服务f 1 2 】。每个接收到突变查询计划的节点都会依据本地的 x m l 数据将查询计划中的某些u r l 替换为相应的x m l 数据，并将这些数据插入到对 应的u r l 节点上。当查询计划中所有的u r l 都得到了替换以后，该查询计划就被执行 完毕了，并被返回给查询请求节点。由于一个突变查询计划被顺序地执行，所以查询处 理的效率较低。但是，突变查询计划可以获得更强的鲁棒性和自治性【l3 1 。这是因为，一 个突变查询计划可以在不同的节点上被重新优化。因此。突变查询处理技术能很好地适 应非结构化p 2 p 环境下的x m l 查询处理。 ( 5 ) 基于r d f 技术的查询处理