广域P2P知识共享和检索系统研究.pptx
《广域P2P知识共享和检索系统研究.pptx》由会员分享,可在线阅读,更多相关《广域P2P知识共享和检索系统研究.pptx(67页珍藏版)》请在咨信网上搜索。
1、OutlinesnText retrieval technologynP2P technologynMotivationnNext work(omited)nReferences(omited)Text retrieval technologynTask of text retrieval system 从大量文本型内容的文档中(信息库)检索某主题信息。例如:搜索引擎nProcess of IR 表达需要的信息;在信息库中检索;返回相关性大的文档集给检索者。Text retrieval technology(续)nDetails of need to consider 如何表达需要的信息?自然
2、语言?词,如SE。文档如何表达成可计算的实体?用不着?量大。用词为之建索引。IF。相关性如何计算?以上三个问题的不同解决对应不同的检索模型Text retrieval technology(续)在文档的用词文档的用词能反映文档的语义前提下(忽略语法,语义等),讨论如下几个检索模型。布尔检索模型 向量空间模型 潜伏语义索引 Text retrieval technology(续)在讨论检索模型之前在讨论检索模型之前:所有索引词集合Terms=Ki ,i=1.N maybe from in all,part or single document文档向量表示:dj=(w1j,w2j,wNj);/N个
3、词,每个词在文档中的权重 wij=Weight(Ki),i=1.N /第i个词的权重由Weight函数给定Text retrieval technology(续)n布尔检索模型 Weight函数为布尔函数。1 if dj in q Sim(dj,q)=0 else 1 if Ki occuring in djwij=Weight(Ki)=0 elseText retrieval(续布尔)Text retrieval(续布尔)n布尔模型存在问题 1、wij没有反映词频 freq(i,j)=索引词汇Ki在dj中出现次数 2、相关性计算结果二值性,决定了不支持部分匹配(有疑义)Text retrie
4、val Technology(续)n向量空间模型 1、用于Web文本检索的标准方法 2、简单,快捷,好方法之一。3、关键思想:针对布尔模型的缺陷。Text retrieval(续向量)nWeight函数(有其他定义)Wij=freq(i,j)max k in terms freq(k,j)wij没有考虑频繁出现在众多文档中的词汇缺乏区分文档的能力!wij=wijlog(M/ni)M:文档总数,ni是ki出现在多少个文档中Text retrieval(续向量)n相关性计算(点积法)dj=(w1j,w2j,wNj)q=(w1q,w2q,wNq)sim(q,dj)=(dj.qT)/(|dj|.|q|
5、)For example:Text retrieval(续向量)Text retrieval(续向量)Text retrieval(续向量)Text retrieval(续向量)n向量空间模型存在问题 1、一词多义 不相关的文档可能被检索到 2、一义多词 相关的,却因为没有含某词而不被检索 问题根源:假定索引词汇的独立性。Text retrieval technology(续)n潜伏语义索引(Latent Semantic Indexing)1、Term-Document矩阵(A)的SVD分解 ANxM=UNxrSrxrVTrxM U,VT相互正交;S对角阵,主对角线上元素(称为single
6、value)从上至下依次递减。U.UT=1;V.VT=1;U称为关键词向量阵,是AAT的特征向量矩阵 VT称为文档向量阵,是ATA的特征向量矩阵Text retrieval(续LSI)(续)矩阵的SVD分解总是存在 复杂性:O(MXNXN)or O(NxMxM)存在近似分解方法。We can also write:A=Sigma(UiSiViT)i=1.r r为秩Text retrieval(续LSI)据需要,选取r,用 A=Sigma(UiSiViT)i=1.r 近似A 即:A:NXM U:NXr VT:rxM 见下页图示:Text retrieval(续LSI)Term Vectors D
7、ocument Vectors Ur Sr VTrAr 是原A的近似,各空间被缩减成Green areaArNxrrxrrxMText retrieval(续LSI)已实现信息库的表达,下面是查询的表达:2、查询表达 映射成缩减的文档向量空间中的向量 因:Ur.UTr=1;Ar=Ur.Sr.VTr Vr=ArUr Sr-1 故:q*=qTUr Sr-1/想象成加入一文档Text retrieval(续LSI)3、Sim(q*,dj)=/dot product4、example(略)注:r的确定可以看|A-Ar|F 是否满足门限要求,但要得到最优的LSI性能,is an open questio
8、ns.但在给定r的情况下,Ar是最好的近似。Text retrieval Technology(续)n评价IR方法的效率 Recall(召回率)=相关文档数/总相关文档数 Precision(准确率)=相关数/查询返回总数 How to calculate?采用人工建立测试集的方法。Text retrieval Technology(续)nRecapitulation1、文本检索任务&过程2、Retrieval model(BoolM,VSM,LSI)3、评价IR方法的效率P2P technology1、Overlay Network 2、What is P2P Computing3、P2P
9、Networks 有址型、无址型4、P2P Applications File Sharing,File Storage,etc.1、Overlay NetworknNetwork 需要考虑:locating(名址),routing,网络拓扑三大问题nOverlay Network 基于若干个现存网络构建 构成一个虚拟的层 解决或缓解底层网络的一些问题。1、Overlay Network(cont.)nInternet is an overlay network 互连各种网络(目标)底层网络可以是以太,令牌,etc.得到一个IP层nBenefits 不必修改现存的协议,可能需要为新的层构造协议
10、。不是每个节点任何时候都需要overlay network服务1、Overlay Network(cont.)nDisadvantages 增添负载(多了一个层,有些功能可能重复如:48bits地址&32bits地址)和层次增多必然带来交互的复杂性。注:因为应用目标需求,而建立overlay network,当然修改现存网络使之适应目标需求也是可行的。例:要实现网络互联。One ON per App?nP2P network is overlay network!Can overlay IP网络 or 实际网络 or?YES!自然三大问题存在。2、What is P2P computingn两
11、节点,进行资源的共享、通信,使用尽可能少的中心控制。这样的计算模式相比于c/s计算,称为p2p计算(对等计算)。节点称为Peer.n为实现某一应用目标,若干peer互连形成一个overlay network,节点间以p2p方式交互。称为:p2p overlay network,简称p2p network.例:Gnutella,Tapstry.What(C/S vs.P2P(cont.)What(C/S vs.P2P(cont.)3、P2P Networks按照对三问题的考虑是否引入 P2P网络层地址(ONLA)分:n有址型P2P network Peer节点有特设的ONLA地址n无址型P2P
12、network Peer节点没有特设的ONLA地址有址型 P2P networknPlaxton,Tapestry,Pastry,CAN,Chord,etc.1.locating e.g.ONLA(Peer)=SHA-1(Peers IP)160bit ONLA地址空间;128bit 对象地址空间 Locating函数就是两空间的确定性映射。2.Routing problem(how get to target?)要是知道目标IP,利用IP层路由算法,不就可以到达目标?类DNS,RAP协议?反函数?有址型(cont.)不“直接”利用IP层路由算法,构建自己的p2p网络路由算法!以Plaxton
13、为例。数据结构:ONLA=0 x4444的 Peer节点路由 (邻居)表 0XXX40XX440X44401XXX41XX441X44412XXX42XX442X44423XXX43XX443X44434XXX44XX444X44445XXX45XX445X44456XXX46XX446X4446有址型(cont.)最长前缀路由算法(类CIDR):假定要从0 x32F8节点到0 x4444.0 x32F8的节点在自己路由表中第一列查找以4开头的地址,假定是4987。然后4987节点在其路由表第二列查找以44开头的地址,假定是4467。类推。即:3278-4xxx-44xx-444x-4444路
14、由表大小及路由长度:O(logN)有址型(cont.)节点加入与离去,路由表构造算法等略。nTapestry,Pastry思想承Plaxton,对节点加入与离去及路由表结构及维护稍有区别。nChord、CAN(omited)无址型 P2P networknNapsterS,GnutellaS,FreenetS,etc.1.没有特设ONLA2.邻居路由表存放IP,按底层IP路由算法到达目标节点。Napster networkn中心目录服务器nLocating(o)=?Routing=?n系统结构存在单点失效问题,可扩展性差面对单点失效n设置多个中心n自我为中心 (O(log2n),O(n2log
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广域 P2P 知识 共享 检索系统 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。