（计算机应用技术专业论文）基于chord的nilsimsa摘要相似性搜索算法.pdf

摘要 摘要 随着信息技术的迅猛发展和流行，针对信息和资源的搜索技术，逐渐在商 业应用和科研领域成为必不可少的技术之一。如：垃圾邮件过滤、图片搜索、 视频搜索，以及信息检索等。目前，搜索应用技术的主要模式限于分类或关键 字检索等。随着近年来使用数据内容( 对象) 进行搜索的应用需求不断增长， 带动了相似性搜索技术的研究与发展。这一类搜索技术通常需要进行复杂的计 算，而且处理的数据量巨大，所以需要可大规模扩展的、分布式的解决方案。 垃圾邮件作为商业广告、恶意程序或敏感内容的载体，对系统安全和人们 的生活造成了严重的影响。本文以大规模数据资源的相似性搜索作为研究出发 点，以基于n i l s i m s a 摘要技术的垃圾邮件过滤应用作为研究对象，提出了一种 适用于大规模的、可扩展的，基于n i l s i m s a 摘要技术的相似性搜索问题解决方 案s s n c 。 s s n c 把高维的n i l s i m s a 摘要数据空间划分成各个子空间，在每个子空间 内采用向量索引的方法，将相似性搜索问题转换为一维空间中的分段搜索问题； 为了分散存储空间和并行化相似查询过程，s s n c 的底层通信平台采用结构化 p 2 p 网络结构c h o r d 。 为了验证文中提出的摘要相似性搜索算法的有效性，本文设计并开发了一 个基于m i t c h o r d 的仿真系统，在此基础之上通过数据发布、查询、负载均衡 等实验，验证了基于n i l s i m s a 摘要的相似性搜索技术可以应用于分布垃圾邮件 过滤领域。 关键词：c h o r d 代表点n i l s i m s a 相似性搜索分布式垃圾邮件过滤 a b s t r a c t ab s t r a c t a st h ei n f o r m a t i o nt e c h n o l o g yd e v e l o p s ，t h es e a r c ha p p l i c a t i o nf o ri n f o r m a t i o n a n dr e s o u r c eg r a d u a l l yb e c o m e so n eo ft h en e c e s s a r yt e c h n o l o g yi nt h eb u s i n e s sa n d r e s e a r c ha r e a s ，s u c ha st h es p a mf i l t e r i n g ，p i c t u r es e a r c h i n g ，i n f o r m a t i o nr e t r i e v a l a n dw e a t h e rf o r e c a s t a tp r e s e n t ，t h em a j o rp a t t e mo fs e a r c ha p p l i c a t i o nl i m i t st ot h e c l a s s i f i c a t i o no rt h el o o k u pb a s e do nk e y w o r d s o nt h eo t h e rh a n d ，t h ei n c r e a s eo f t h ed e m a n df o rt h ei n f o r m a t i o nl o o k u pb a s e do nd a t ac o n t e n t ( o b j e c od r i v e st h e q u i c kd e v e l o p m e n to fs i m i l a r i t ys e a r c h t h ec o m p l e xc o m p u t i n ga n dt h em a s s i v e d a t aa r et w oi m p o r t a n tp r o b l e m sf o rs i m i l a r i t ys e a r c h t h e r e f o r e ，t h es i m i l a r i t y s e a r c ha p p l i c a t i o nr e q u i r e st h es c a l a b l ea n dd i s t r i b u t e ds o l u t i o nt oh a n d l et h e s e p r o b l e m s a st h ec a r r i e ro fb u s i n e s sa d v e r t i s e m e n t s ，m a l i c i o u sp r o g r a m so rs e n s i t i v e c o n t e n t ，s p a mi m p a c t st h es e c u r i t yo fc o m p u t e rs y s t e ma n dp e o p l e sl i f es e r i o u s l y t of i l t e rt h es p a m ，t h i sd i s s e r t a t i o np r o p o s e sal a r g e s c a l ea n ds c a l a b l es i m i l a r i t y s e a r c hs o l u t i o ns c h e m eb a s e do nt h en i l s i m s ad i g e s tt e c h n o l o g y b ya d o p t i n gt h e v e c t o ri n d e xm e t h o d ，t h es c h e m ec o n v e r t st h es i m i l a r i t ys e a r c hp r o b l e mt ot h e s e g m e n ts e a r c hp r o b l e mi no n ed i m e n s i o n t h es c h e m ei sb u i ko nt h et o po f s t r u c t u r e dp 2 pn e t w o r kc h o r d ，t od i s t r i b u t et h ei n f o r m a t i o ns t o r a g et on o d e si nt h e n e t w o r ka n dp a r a l l e lt h el o o k u pp r o c e d u r e t oe v a l u a t et h e e f f e c t i v e n e s so ft h es e a r c h i n ga l g o r i t h mb a s e do nd i g e s t s i m i l a r i t y ，w ed e s i g nap r o t o t y p es y s t e mb a s e do nm i t c h o r d t h r o u g ht h e e x p e r i m e n t sb yt h ep r o t o t y p es y s t e m ，s u c ha sd a t ap u b l i s h i n g ，q u e r y i n ga n dl o a d b a l a n c i n g ，w ep r o v et h ee f f e c t i v e n e s so ft h ep r o p o s e ds i m i l a r i t ys e a r c h i n ga l g o r i t h m b a s e do nn i l s i m s ad i g e s to ns p a mf i l t e r i n g k e yw o r d s ：c h o r d ，d e l e g a t e ，n i l s i m s a , s i m i l a r i t ys e a r c h ，d i s t r i b u t e ds p a mf i l t e r 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 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年月日 南开大学研究生学位论文作者信息 论文题目 姓名学号答辩日期年月日 论文类别 博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院系所 专业 联系电话e m a i l 通信地址( 邮编) ： 备注：是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言 第一节课题背景 随着信息技术的迅猛发展，无论是在商业应用还是在科研领域，都出现了 大量针对( 文本) 信息和( 多媒体) 数据的新的搜索需求，这类搜索的目的是 搜索与给定对象( 图片【1 1 、邮件 2 1 、视频【3 1 等) 相似的数据。而这些数据最显著 的特征就是由原来的单一属性或低维属性向高维属性转化。处理这一类相似性 搜索问题可以采用传统的基于属性的搜索，但是这样往往会导致多维向量空间 中的复杂查询。于是，对高维数据的处理，尤其是高维空间中数据之间的相似 性度量也随之成为众多应用领域所面临的一个重要问题，这些领域包括数据挖 掘、信息处理与检索、决策支持等1 7 j 。 通常的多维向量空间中的复杂查询，可以使用k d t r e e t 4 与q u a d t r e e t s l 等索引 结构进行处理，但对于高维数据空间则显得力不从心，而高维又恰恰是相似性 搜索中需要处理的数据对象的基本特征。这些挑战促进了基于度量的相似搜索 的发展。这类方法将数据空间看作度量空间，数据集与距离函数适用于每一对 数据对象。这种模型中的查询被定义为查询样本与相似度1 8 9 j 。但是，相似搜索 的代价是高昂的，而且与数据集的大小呈线性关系。因此如果处理的数据量很 大，则需要采用分布式技术来处理，以实现数据的分布式存储和查询的并行化 处理【l o ，14 1 。 中国互联网络信息中一t , ( c n n i c ) 0 9 年1 月发布了第2 3 次中国互联网络发 展状况统计报告【1 6 】，截止2 0 0 8 年底我国i n e m e t 网民的规模已经超过美国，接 近有3 亿。较2 0 0 7 年增长4 1 9 ，互联网普及率达到2 2 6 ，略高于全球平均 水平( 2 1 9 ) 。伴随着网络的迅速普及，互联网已成为人们生活中不可缺少的组 成部分，电子邮件成为继书信、电报、电话之后的又一主要通讯方式，在现代 社会中扮演着越来越重要的角色，无论是普通用户还是企业公司都会同时拥有 若干个电子邮件地址。根据中国互联网协会反垃圾邮件中心公布的( ( 2 0 0 8 年第 三次反垃圾邮件报告【l 刀，截止2 0 0 8 年1 2 月，中国活跃的邮箱账号为6 亿多。 随着电子邮件服务覆盖范围日益扩大，与人们日常工作生活联系也日趋紧密。 第一章引言 正是由于电子邮件的这种普遍性，以及发送成本的低廉性使其成为一些广告商 和不法分子的利用工具，垃圾邮件开始充斥人们的电子邮箱，甚至影响正常的 生活与工作。 根据( 2 0 0 8 年第三次反垃圾邮件报告，中国网民平均每周收到垃圾邮件的 数量为1 7 8 6 封，与去年同期相比，增加1 1 7 封，增幅为7 0 1 中国网民平均 每周收到垃圾邮件的比例为5 7 8 9 ，与去年同比上升了2 0 4 个百分点。垃圾 邮件内容主要涉及到零售业推销、旅游交通业推销、违法出售票据证件、恶意 软件链接、病毒等传播方面。 另据s y m a n t e c 公司公布的2 0 0 8 年3 月份垃圾邮件现状报告【1 8 】，在全球范围 内，垃圾邮件的数量在2 0 0 8 年一、二月份保持稳定，连续两个月维持在所有邮 件数量的7 8 5 。这比2 0 0 7 年上半年的平均6 1 有所上升。由此可知，对垃 圾邮件的处理已经达到刻不容缓的地步。 第二节当前的解决方案 近年来，反垃圾邮件技术一直处在不断地快速发展中，并在一定程度上有 效地遏制了垃圾邮件泛滥的趋势，但是依然面临着很大的压力。为了彻底解决 垃圾邮件的问题，有人提出了反垃圾邮件立法。一旦确认某个团体或个人是垃 圾邮件的发送者，那他就面临着法律的制裁与处罚；或者规定发送任何邮件都 要付出一定的“邮票”代价，以此来制约垃圾邮件发送者大规模重复的发送邮 件。针对目前垃圾邮件泛滥的现状，反垃圾邮件立法的呼声虽然日益渐高。但 立法面临着一系列的问题。首先是垃圾邮件的概念之争，到底什么是垃圾邮件， 像宣传品、电子期刊等这类邮件是不是垃圾邮件很难界定，垃圾邮件发送者会 想尽一切办法逃脱法律的惩罚；其次是法律的执行问题，给予什么样的处罚， 而且如果缺少国际合作，即使发现来自境外的垃圾邮件，也无法制裁。如果规 定发送邮件都需要一定的额外代价，在现阶段显然很难得到广大邮件用户的认 可。 目前反垃圾邮件最有效的方法就是通过技术手段来实现。d r n e a k r a w e t z 在 文章 1 9 】中对反垃圾邮件技术作了详细的综述，并将当前的反垃圾邮件技术分 为了四大类：过滤、反向查询、挑战和证书。从应用情况来看，过滤技术是使 用最为广泛的，比如很多邮件服务器上的反垃圾邮件插件、反垃圾邮件网关， 2 第一章引言 客户端上的反垃圾邮件插件等，都是采用过滤技术。垃圾邮件过滤技术主要通 过复杂的规则或策略来辨别和处理垃圾邮件。目前常使用的过滤技术有很多种， 大致可以分为传统的垃圾邮件过滤技术和新兴的分布式协同过滤技术两个类 别。 1 2 1 传统的过滤技术 有关垃圾邮件过滤技术的研究已经兴起了很多年，相关的投入也很大，涌 现了一大批相关产品。传统的垃圾邮件过滤技术主要有：黑白名单过滤，关键 字过滤、h a s h 技术、基于规则的过滤，基于概率的过滤等等。 传统的垃圾邮件过滤技术，主要是依据电子邮件自身的结构特点进行设计。 邮件的协议和内容格式是由r f c 的几个文档规定的。r f c8 2 1 规定了s m t p ， 定义了发送邮件的机制。r f c1 7 2 5 规定了p o p 3 ，定义从p o p 3 服务器收取邮 件的机制。r f c8 2 2 定义邮件格式。随着电子邮件的广泛使用，邮件系统不仅 需要传输各种字符集的文本内容，而且还需要传送各种非文本文件( 例如图像 文件、w o r d 文件、p d f 文件、z i p 文件等) ，根据这样的需求，人们又定义了 m i m e 标准，作为r f c8 2 2 的补充。它由r f c1 5 2 1 和r f c1 5 2 2 这两个标准构 成。目前几乎所有的邮件服务系统都支持m i m e 标准。 基于规则的过滤方法1 2 0 】从电子邮件的结构出发，寻找垃圾邮件的特征，在 发件人、收件人、邮件头等各方面展开邮件过滤工作，是垃圾邮件过滤常采用 的基本方法，这些方法主要包括：s m t p 用户认证，实时黑名单过滤和可信白 名单，设定过滤规则( 信头分析，群发过滤，关键字匹配) 等，它们在一定程 度对垃圾邮件的泛滥起到抑止作用。 但是，基于规则的过滤方法也有其不足之处。例如，通常情况下，并不是 某几个固定的发件人在发送垃圾邮件，而是发送者在不断地变化，这样使用黑、 白名单方法就有局限性。基于规则的方法需要人们不断去发现和总结、更新规 则，人为因素较多，一些没有经验的用户可能很难提供有效的规则。而且，手 工制定规则比较耗时，准确率也受到了限制。随着时间的变化，垃圾邮件的特 征也在变化，让用户维护这些规则也不是一件易事。 所谓的基于概率的过滤是指采用文本分类算法分析邮件正文中所包括的文 本信息，计算该文本属于不同类别的概率，进而对邮件属性进行判断的方法。 3 第一章引言 目前，在邮件分类领域中使用的分类算法主要有贝叶斯方法【2 2 1 、k 近邻方法【2 3 】、 支持向量机【2 4 1 、神经网络【2 5 】等。其中，贝叶斯方法以其良好的分类准确性，分 类速度成为应用最为广泛的方法。 i b m 的研究报告指出：“文本信息占现存电子邮件信息总量的8 0 以上”。 随着因特网的发展，多媒体信息数量日益增加，但是文本信息依然是人们在因 特网中获得信息的最主要途径。因此，利用文本信息处理技术( 主要是文本分 类方法) 对垃圾邮件的内容进行识别的邮件过滤方法逐渐成为反垃圾邮件技术 的主流。基于概率理论类技术，通常首先需要收集垃圾邮件和正常邮件样本集， 通过对样本集的训练，得到邮件特征库，进而根据特征库对目标邮件内容进行 甄别。因此，这种方法具有滞后性特征，新的垃圾邮件很容易突破过滤规则的 检测。这种算法受训练集的限制，在准确率和查全率方面也难以达到令人满意 的程度。另外，垃圾邮件发送者使用的垃圾邮件技术也在推陈出新，有的甚至 使用图像来传输邮件内容，这样，基于内容的过滤技术就完全失效了，因为它 们无法识别图像上有什么信息。 实际应用中，仅凭一两种过滤方式很难达到阻止绝大部分垃圾邮件的目的。 需要将关键字过滤、黑白名单过滤、规则过滤等多种过滤方式结合起来，通常 的处理过程为：“截获样本，解析特征，生成规则，规则下发，内容过滤 等。 但是由于垃圾邮件数量巨大，并且垃圾邮件的类型干变万化，传统的过滤技术 存在着一些不可避免的先天缺陷。 首先，由于垃圾邮件内容特征变化很快，而且处在一种多语种高爆发频率 状态，所以，关键字的规则是很难维护的，而且是一种滞后的被动变化的处理 方法。其次，传统的垃圾邮件过滤的一般过程为：先对邮件进行内容过滤，再 用贝叶斯法评分，然后归档分类为垃圾邮件、可疑邮件和正常邮件。完成过滤 过程需要经历的步骤太多，以致于过滤的效率非常低。 1 2 2 分布式协同过滤技术 由于垃圾邮件发送者总是在短时间内向大量的邮件账号密集的发送垃圾邮 件口6 1 ，因此不难想象垃圾邮件具有地域上的发散性和时间上的突发性。当一个 邮件服务器收到一封垃圾邮件的时候，很多其他的服务器也会在短时间内收到 相似的邮件。这些相似的垃圾邮件都是同二封邮件的副本或者变体，其中的差 4 第一章引言 异是垃圾邮件发送者刻意制造的，目的就是为了躲避垃圾邮件网关的检测。传 统的垃圾邮件过滤技术不论是基于规则的还是基于概率的，都是单机系统，各 个邮件服务器各自为政，它们都无法利用垃圾邮件的这些全局的特性。 分布式垃圾邮件过滤技术是由多个垃圾邮件过滤器组成的垃圾邮件过滤网 络，各个过滤器之间通过网络交换垃圾邮件数据，以更加准确地识别垃圾邮件。 由于通过多个过滤器所积累的垃圾邮件数据非常丰富，能够很好地利用垃圾邮 件分布的全局特性。因此，分布式邮件过滤技术对垃圾邮件的识别能力比较高。 分布式邮件过滤技术正是目前研究的热点，许多学者和反垃圾邮件研究机构已 参与到此研究领域中1 3 2 ，乃j 。 d c c ( d i s t r i b u t e dc h e c k s u mc l e a r i n g h o u s e ) t 2 9 】采用分布式目录来存储邮件的 校验值( 校验值类似于摘要、签名) 。邮件用户和i s p 可以将收到邮件的校验值( 而 不是邮件内容本身) 提交给d c c d e 多台开放的服务器。开放的服务器记录相同校 验值的提交次数即同一封邮件被提交的次数。通过对开放的服务器的请求，用 户可以知道某一封邮件已经被其他用户收到的次数n 。如果n 大于用户自己设定 的阈值，d c c 客户端可以标记其为垃圾邮件或者选择直接丢弃。d c c 较好地考 虑了用户的隐私，不过并没有过多地考虑安全问题。比如恶意用户可以利用 d c c 客户端来通知d c c j 艮务器已经收到过某一封邮件很多次，这样其他的d c c 客户端对这封邮件容易产生误判。另外d c c 所采用的校验值技术是对邮件进行 去噪处理后，对邮件内容的某些特定部分产生哈希值。与其他一些摘要技术相 比，这种校验值技术抗攻击能力较差。 v i p u l sr a z o r t 3 0 】是一个基于客户端日艮务器结构的分布式垃圾邮件过滤器。 与d c c 不同的是，r a z o r 不是由客户端上报所有邮件的指纹，而是要求人工上报 确认的垃圾邮件。如今r a z o r 已经从一个开源的项目转化为一个商业的系统 s p a m n e t t 3 1 】。它使用一个中心的服务器保存已知垃圾邮件指纹的目录。当用户 将一封邮件识别为垃圾邮件后，这封邮件的指纹被发送到中心服务器。这样在 中心服务器就可以积累大量的垃圾邮件指纹。当用户接收到邮件时，s p a m n e t 客户端连接到中心服务器，来判断该邮件是否为垃圾邮件。如果在中心服务器 的垃圾邮件目录中找到了这个指纹的记录，就可以将其判断为垃圾邮件。中心 服务器根据用户以往的垃圾邮件识别准确程度给用户赋予相应的“声誉值 ，对 于“声誉值”高的用户识别的邮件指纹赋予大的权重。在用户数量比较多而且 举报率较高的情况下，s p a m n e t 可以取得不错的过滤效果；然而，由于s p a m n e t 5 第一章引言 基于客户端服务器的结构工作，它存在单点故障的问题，即当辨别垃圾邮件的 请求很多时，服务器可能会出现阻塞和瘫痪的情况。 f e n gz h o u 在文章 3 2 】中提出了一种在p 2 p 网络中发布邮件摘要的方法，并 支持有效的近似检索，p 2 p 网络中的结点可以通过近似查询，得到网络中与给 定查询摘要相似的所有摘要，并将相似摘要的数目作为判别垃圾邮件的依据。 它所使用的是一种称为1 0 维向量的摘要，摘要算法以一个5 0 字节大小的窗口 沿着文本滑动，每次向后移动一个字符，当每次移动后，对窗口中的字符进行 哈希运算，得到一个整数，称为指纹( f i n g e r p r i n t ) 。当所有的指纹计算出来后， 从中选取最大的1 0 个作为该文本的摘要。这种摘要算法有一个很大的缺陷，它 不能抵挡垃圾邮件发送者针对算法的攻击。垃圾邮件发送者可以在邮件的最后 加上一段字符串，而这一段字符串经过巧妙的设计，可以使在这段字符串上的 窗口产生的指纹刚好具有某种特性，使得它们更有可能被选到最终的特征向量 里面去。 e d a m i a n i 在文章 3 3 】中提出了n i l s i m s a 摘要算法，n i l s i m s a 是一种本地敏 感的哈希函数，它以一个文档作为输入，输出一个刀比特的摘要值。e d a m i a n i 详细分析了n i l s i m s a 在反垃圾邮件应用中的参数选择、准确性、安全性等具体 问题，并证实了它的有效性。在文章 3 4 】中e d a m i a n i 提出了一种基于n i l s i m s a 摘要算法的分布式垃圾邮件处理系统。该系统使用三层结构来实现垃圾邮件的 协作式检测和过滤。用户处于第三层，负载向所属的邮件服务器报告其所收到 的垃圾邮件信息。邮件服务器处于第一层和第二层，采用拥有超级结点的p 2 p 网络来实现垃圾邮件摘要信息的分布式共享。某些高性能服务器被设定为处于 第一层的超级结点，处于第二层的普通结点发送垃圾邮件报告给与其相连的超 级结点，并从超级结点请求某些可疑邮件是否被其他结点认定为垃圾邮件。所 有的摘要信息只存储在超级结点上，超级结点间通过某种方式互联并交换信息。 这种系统的最大的缺点是n i l s i m s a 摘要在所有超级结点上的分布没有任何规 律，每次普通结点针对某个摘要发起的查询都可能涉及所有的超级结点。由于 n i l s i m s a 摘要的数目非常庞大，而且由于n i l s i m s a 摘要的特殊性，查询难以采 用排序等方式进行优化，使得超级结点的负载很大，系统的可扩展性比较差。 d h t n i l e 2 8 】是一种基于d h t 的邮件n i l s i m s a 摘要发布与查询方法。它采用向 量空间划分的办法，将相似的n i l s i m s a 摘要数据归并到一个或者几个子空间中， 而后使用子空间中的代表点将n i l s i m s a 摘要发布n d h t 网络中少数几个节点 6 第一章引言 中，并利用摘要与代表点的远近关系可以进行有效地近渐查询。d h t n i l 系统中 摘要的发布、查询、和存储都是分布式的。d h t n i l 突破了传统的n i l s i m s a 摘要 总是集中处理的缺陷，使得系统具有更好的扩展性。但是由于d h t n i l 对子空间 内的数据并没有作区分，使得系统中各个节点在子空间内数据不断增大时，查 询效果并不是很好。 第三节本文研究内容 分布式垃圾邮件处理技术已经是垃圾邮件过滤领域的一个研究热点。在分 布式垃圾邮件处理系统中，摘要算法至关重要。相关的研究【3 3 1 和实践【3 0 】【3 5 】已经 证明了n i l s i m s a 算法在垃圾邮件处理中的有效性。但是至今为止研究人员提出 的基于n i l s i m s a 算法的垃圾邮件处理系统多使用集中式的方式来存储和查询摘 要，系统的性能和扩展很差。即使是采用了分布式技术来处理摘要存储和查询 的系统，系统的运行效率依然很低。如文章 3 3 】提出的基于n i l s i m s a 摘要算法的 分布式垃圾邮件处理系统，虽然所有的n i l s i m s a 摘要分布于所有的超级结点中， 但由于其分布并没有规律，使得查询的时候将涉及所有的超级结点，因此超级 结点的负载还是很重，这使得系统的可扩展性很差。 通过近几年的努力，相似数据搜索领域取得了长足的进步。这类搜索机制 的目的是搜索与给定对象( 图片、邮件、视频等) 相似的数据。基于n i l s i m s a 摘要的垃圾邮件过滤过程，即就是对n i l s i m s a 摘要进行相似性搜索的过程。 n i l s i m s a 摘要的基本特征是其数据存在于高维数据空间，如果采用传统的基于 搜索机制，往往会导致多维向量空间中的复杂查询。在研究n i l s i m s a 摘要的基 础上，本文提出了一种适用于大规模的、可扩展的、基于n i l s i m s a 摘要技术的 相似性搜索问题解决方案：s s n c ( s i m i l a r i t ys e a r c ho f n i l s i m s ad i g e s t si nc h o r d ) 算法，该算法使用向量索引的方法，将高维数据的相似性搜索问题转换为一维 空间中的分段搜索问题，网络结构采用c h o r d 协议，以分散存储空间和并行化 相似性查询过程。s s n c 将相似的n i l s i m s a 摘要集中发布到c h o r d 网络中的同 一个或少数几个结点上。在查询的时候，也只需要查询少数的一些结点就可以 查询到绝大多数的相似摘要。摘要的发布、存储和近似查询都是完全分布式的， 突破了传统n i l s i m s a 摘要集中式的存储与查询方式的缺陷，并且根据摘要之间 的相似特征，将摘要在c h o r d 网络中有规律的存储，使用系统的性能得到很大 7 第一章引言 的提高。 本文详细论述了基于c h o r d 的n i l s i m s a 摘要相似性搜索算法s s n c 。摘要 发布时使用向量空间划分的办法将摘要归到各个子空间，然后通过子空间内的 代表点为摘要计算相似距离后，将摘要发布到c h o r d 网络中。相似摘要的查询 相对于摘要发布要复杂一些。文中提出了三种相似摘要的查询算法，在这些算 法中都使用了基于老化算法的渐进式范围查询。本文的第四章和第五章将详细 介绍算法的设计细节和仿真系统中的实现方法，以及执行过程。 在本文的最后，我们通过模拟实验验证了s s n c 算法的有效性。实验部分 重点测试n i l s i m s a 摘要的发布算法和查询算法的性能，并对系统的负载均衡进 行了验证。 第四节论文结构 本文共分6 部分，具体的结构如下： 第一章介绍课题的研究背景和当前研究的现状，已有方案存在的缺点以及 本文的研究内容； 第二章简要介绍c h o r d 网络协议，实验仿真系统的一些基础工作； 第三章简要介绍相似性度量的方法，n i l s i m s a 摘要算法，以及对n i l s i m s a 摘要算法的改进等； 第四章详细论述基于c h o r d 的n i l s i m s a 摘要相似性搜索算法： 第五章主要介绍了实验仿真系统的设计和实现细节，以及系统的特性等； 第六章通过实验评价摘要发布和查询的性能以及其负载均衡特性； 第七章对算法的特点及性能加以总结，并给出进一步完善的建议。 8 第二章研究基础 第二章研究基础 第一节c h o r d 网络环境 c h o r d 网络是一种结构化p 2 p 网络，本节首先对p 2 p 的概念和分类进行简 单的描述，然后对结构化p 2 p 网络的关键技术和不同拓扑结构的d h t 算法进 行介绍，最后简要阐述c h o r d 网络。 2 1 1p 2 p 概述 p 2 p b p “点对点一网络，也称为对等网( p e e rt op e e r ) 。p 2 p 网络打破了传 统的c s 模式，网络中的每个节点的地位都是对等的。每个节点既充当服务器， 为其他节点提供服务，同时也享用其他节点提供的服务【3 6 】。相比传统的 c l i e n t s e r v e r 模式而言，p 2 p 具有自己鲜明的特点和优势。 p 2 p 网络按照拓扑结构可以简单地分为两大类【3 7 】：结构化p 2 p ( s t r u r t e u r t e d t o p o l o g y ) 和无结构化p 2 p ( u n s t r u r t e u r t e dt o p o l o g y ) 。其中无结构化p 2 p 网络根 据是否有中央服务器进行集中管理，又可划分为集中式( c e n t r a l i z e dp 2 p ) 、分 布式( d e c e n t r a l i z e dp 2 p ) 和混合式( h y b r i dp 2 p ) 三种不同模式。本文中使用 的c h o r d 网络一种结构化p 2 p 的网络，下一节中我们将重点介绍结构化p 2 p 网络 d h t 。 2 1 2 结构化p 2 p 结构化p 2 p ，又称为d h t ( d i s t r i b u t eh a s ht a b l e ) 3 8 】网络，是一种完全分布 式的p 2 p 网络。d h t 是一个由大量结点共同维护的巨大散列表，散列表被分 割成不连续的块，每个结点保存并管理一个属于自己的散列块。d h t 结构能 够自适应结点的动态加入退出，有着良好的可扩展性、鲁棒性、结点i d 分配 的均匀性和自组织能力，同时由于采用了确定的拓扑结构，d h t 可以提供精 确的发现功能。只要目标资源存在于网络中，d h t 总能发现它，发现的准确 性得到了保证。 9 第二章研究基础 在这样的系统中，每个资源拥有一个资源号：r e s o u r c e i d ，r e s o u r c e - i d 是 通过h a s h 资源的参数形成，是资源的唯一标识。p 2 p 覆盖网中的每一个结 点也有一个i d ，称作是n o d e i d ，n o d e i d 和r e s o u r c e i d 使用相同的h a s h 值空间，统称为关键字( k e y ) 。每个结点除了可靠的保存所有和自己n o d e i d 相 接近的r e s o u r c e i d 的资源信息，还需要保存少数的其他结点位置信息。当用 户想查找资源信息时，他将根据资源的r e s o u r c e i d 向n o d e i d 与该 r e s o u r c e i d 相接近的结点发出查找请求。如果那个结点没有保存资源信息， 他将返回一个n o d e i d 与r e s o u r c e i d 更接近的结点信息，由原结点继续发 出查找请求。通过这样的机制，查找请求信息将最终到达保存该资源信息的结 点，并由该结点回应查找请求。当结点加入或者离开时，结点之间相互通信用 以保持完整的d h t 结构和交换存储的资源信息。不同的d h t 算法执行不同 的拓扑结构，如：c h o r d 3 9 1 是一个环形结构、c a n l 4 0 】是一个n 维向量空间的栅 格结构、p a s t r y 4 1 1 和t a p e s t r y 4 2 则是网状拓扑结构等等。多篇文章对d h t 网络的 可靠性、可用性、安全性进行了深入的研究，d a v i d 等在文章 4 3 1 中评估t d h t 网络的性能，e m i l 等在文章 4 4 】中探讨了d h t 网络的安全问题和保护方法，j o s h 在文章 4 5 】中研究了d h t 的可靠性和健壮性问题。本文提出的n i l s i m s a 摘要相似 性搜索算法将建立在c h o r d 网络结构之上，在下一节中将对c h o r d 做简要的介绍。 2 1 3c h o r d 网络 p 2 p 系统是一种没有中央控制和分层组织的系统，系统中每个节点在功能 上处于同等地位，不同的p 2 p 系统具有不同的特性，但在大部分的p 2 p 系统中如 何有效地定位数据仍然是关键问题。2 0 0 1 年由麻省理工学院提出t c h o r d l 3 9 1 ， 其核心思想就是要解决在p 2 p 应用中遇到的基本问题：如何在p 2 p 网络中找到存 有特定数据的节点。 c h o r d 采用了相容哈希【4 6 】的一个变体为结点分配关键字( k e y ) ，所有节点 按照其节点标识符从小到大( 取模2 m 后) 沿着顺时针方向排列在一个逻辑的标 识圆环上。c h o r d 实现了这样种操作：给定一个k e y ，将k e y 映射到某个结 点。如果给对等网络应用的每个数据都分配一个k e y ，那么对等网络中的数据 查找问题就可以用c h o r d s 艮容易地解决了。在c h o r d 中，结点并不需要知道所 有其他结点的信息。每个c h o r d 结点只需要知道关于其他结点的少量的“路由 1 0 第二章研究基础 信息。在由n 个结点组成的网络中，每个结点只需要维护其他0 ( 1 0 9 n ) 个 结点的信息，同样，每次查找只需要0 ( 1 0 9 n ) 条消息。当结点加入或者离开 网络时，c h o r d 需要更新路由信息，每次加入或者离开需要传递0 ( 1 0 9 2 ) 条消息。 在c h o r d 中，每个关键字都保存在它的后继( s u c c e s s o r ) 结点中，后继结点 是结点标识符大于等于关键字k 的第一个结点，我们将其记为s u c c e s s o r ( k ) 。如果 标识符采用m 位二进制数表示，并且将从o 到2 加一1 的数排列成一个圆圈，那 么s u c c e s s o r ( 七) 就是从七开始顺时针方向距离最近的结点。 1 关键字查找 在c h o r d 中，每个结点维护少量的路由信息，通过这些路由信息，可以提高 查询的效率。如果m 是关键字和结点标识符的位数( 采用二进制表示) ，那么每 个结点只需要维护一张最多m 个表项的路由表，我们称之为指针表( f i n g e r t a b l e ) 。结点刀的指针表的第f 个表项包括的是严s u c c e s s o “刀+ 2 卜1 ) ，这里1 f m 并且所有的计算都要进行r o o d2 历，s 称为结点行的第f 个指针，我们用 g f i n g e r i n o d e 表示，指针表中的其他项的含义如表2 1 所示。 表2 1c h o r d 指针表表项 符号定义 如l埘 f i n g e r 明s t a r t 0 + 2 ) m o d2 ，1 k 肌 f i n g e r 明i n t e r v a lf f i n g e r k s t a r t ，f i n g e r k + 11 s t a r t l f i n g e r 纠n o d e 第一个大于等于7 f i n g e r 明s t a r t 的结点 s u c c e s s o r 标识符环中的下一个结点；等于f i n g e r 1 n o d e p r e d e c e s s o r 标识符环中的前一个结点 以图2 5 为例，结点l 的指针表的表项应该分别指向标识符( 1 + 2 0 ) m o d2 3 = 2 ，( 1 + 2 n ) m o d2 3 = 3 ，( 1 + 2 2 ) m o d2 3 = 5 。而标识符2 的后继是结点3 ，因为 它是2 之后的第一个结点，标识符3 的后继是结点3 ，而标识符5 的后继是结 点0 。 这一方案有两个重要的特性：首先，每个结点都只需要知道一部分结点的 信息，而且离它越近的结点，它就知道越多的信息。其次，每个结点的指针表 通常并不包括足够的信息可以确定任意一个关键字的位置。例如，图2 6 【3 9 】中 第二章研究基础 的结点3 就不知道关键字1 的位置，因为1 的后继结点信息并没有包含在结点 3 的指针表中。 图2 1c h o r d 数据组织实例 当结点n 不知道关键字是的后继结点时怎么办? 如果n 能够找到一个结点， 这个结点的标识符更接近乜那么这个结点将会知道该关键字的更多信息。根 据这一特性，n 将查找它的指针表，找到结点标识符大于七的第一个结点i ，并 询问结点，看，是否知道哪个结点更靠近后。通过重复这个过程， 1 最终将会 知道后的后继结点。 2 新结点的加入 结点腮的加入分为三个阶段。 1 ) 初始化新结点的指针表。 假设结点n 在加入网络之前通过某种机制知道网络中的某个结点刀。这时， 为了初始化刀的指针表，以将要求结点刀，为它查找指针表中的其他表项。 2 ) 更新现有其他结点的指针表。 结点加入网络后将调用其他结点的更新函数，让其他结点更新其指针表。 3 ) 从后继结点把关键字传递到结点刀。 这一步是把所有后继结点是门的关键字转移n n 上。整个加入操作的时间复 1 2 第二章研究基础 杂度是0 ( 1 0 9 2 n ) ，如果采用更复杂的算法，可以把复杂度降低到d ( 1 0 9 n ) 。 3 结点的失效处理 在对等网络中，某个对等结点随时可能退出系统或者发生失效，因此处理 结点失效是一个重要的问题。在c h o r d 中，当结点刀失效时，所以在指针表中 包括行的结点都必须把刀替换成n 的后继结点。另外，结点玎的失效不能影响 系统中正在进行的查询过程。 在失效处理中最关键的步骤是维护正确的后继指针。为了保证这一点，每 个c h o r d 结点都维护一张包括，个最近后继的后继列表。如果结点疗注意到它 的后继结点失效了，它就用后继列表中第一个正常结点替换失效结点。 第二节m i t c h o r d 系统 为了验证本文中提出的摘要相似性搜索算法，我们设计并实现了一个类似 于开源项目m i t - c h o r d 6 1 j 的实验系统s s d c ( s i m i l a r i t ys e a r c ho fd i g e s t si n c h o r d ) 4 8 】，并在著名的开源网站s o u r c e f o r g e 以s s d c 为项目名称为该系统创建 了一个开源项目。s s d c 中只保留了m i t - c h o r d 系统的消息路由模块和数据持久 化模块，修改了其中c h o r d 协议库的键值管理，添加了新的数据分布式存储与共 享库，并在数据管理层添加了类似于r a d i x 搜索树的索引结构。这一节的余下内 容将简要介绍m i t - c h o r d 的系统功能和各模块使用的技术；下一节介绍r a d i x 搜 索树年f i b