《广域p2p知识共享和检索系统研究》由会员分享，可在线阅读，更多相关《广域p2p知识共享和检索系统研究（68页珍藏版）》请在金锄头文库上搜索。
1、广域P2P知识共享和检索系统研究,肖明忠 北京大学计算机科学技术系 网络与分布式系统实验室 2002-11-29 10:00-11:00,Outlines,Text retrieval technology P2P technology Motivation Next work (omited) References (omited),Text retrieval technology,Task of text retrieval system 从大量文本型内容的文档中（信息库）检索某主题信息。例如：搜索引擎 Process of IR 表达需要的信息； 在信息库中检索； 返回相关性大的文档集
2、给检索者。,Text retrieval technology(续),Details of need to consider 如何表达需要的信息？ 自然语言？词，如SE。 文档如何表达成可计算的实体？ 用不着？量大。用词为之建索引。IF。 相关性如何计算？ 以上三个问题的不同解决对应不同的检索模型,Text retrieval technology(续),在文档的用词能反映文档的语义前提下（忽略语法，语义等），讨论如下几个检索模型。 布尔检索模型 向量空间模型 潜伏语义索引,Text retrieval technology(续),在讨论检索模型之前： 所有索引词集合Terms=Ki ，i=1
3、N maybe from in all,part or single document 文档向量表示： dj=(w1j,w2j,wNj); /N个词，每个词在文档中的权重 wij=Weight(Ki), i=1N /第i个词的权重由Weight函数给定,Text retrieval technology(续),布尔检索模型 Weight函数为布尔函数。 1 if dj in q Sim(dj,q)= 0 else,1 if Ki occuring in dj wij= Weight(Ki)= 0 else,Text retrieval (续布尔),Text retrieval (续布尔),布尔
4、模型存在问题 1、wij没有反映词频 freq(i,j)=索引词汇Ki在dj中出现次数 2、相关性计算结果二值性，决定了不支持部分匹配(有疑义),Text retrieval Technology(续),向量空间模型 1、用于Web文本检索的标准方法 2、简单，快捷，好方法之一。 3、关键思想： 针对布尔模型的缺陷。,Text retrieval (续向量),Weight函数(有其他定义) Wij= freq(i,j) max k in terms freq(k,j) wij没有考虑频繁出现在众多文档中的词汇缺乏区分文档的能力！ wij=wijlog(M/ni) M:文档总数，ni是ki出现在
5、多少个文档中,Text retrieval (续向量),相关性计算（点积法） dj=(w1j,w2j,wNj) q=(w1q,w2q,wNq) sim(q,dj)=(dj.qT)/(|dj|.|q|) For example:,Text retrieval (续向量),Text retrieval (续向量),Text retrieval (续向量),Text retrieval (续向量),向量空间模型存在问题 1、一词多义 不相关的文档可能被检索到 2、一义多词 相关的，却因为没有含某词而不被检索 问题根源：假定索引词汇的独立性。,Text retrieval technology(续),
6、潜伏语义索引（Latent Semantic Indexing) 1、Term-Document矩阵（A）的SVD分解 ANxM=UNxrSrxrVTrxM U,VT相互正交；S对角阵，主对角线上元素（称为single 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=1r
7、r为秩,Text retrieval(续LSI),据需要，选取r,用 A=Sigma(UiSiViT) i=1r 近似A 即：A:NXM U:NXr VT:rxM 见下页图示：,Text retrieval(续LSI),Term Vectors Document Vectors Ur Sr VTr Ar 是原A的近似，各空间被缩减成Green area,Ar,Nxr,rxr,rxM,Text retrieval(续LSI),已实现信息库的表达，下面是查询的表达： 2、查询表达 映射成缩减的文档向量空间中的向量 因：Ur.UTr=1 ；Ar=Ur.Sr.VTr Vr= ArUr Sr-1 故：
8、q*=qTUr Sr-1 /想象成加入一文档,Text retrieval(续LSI),3、 Sim(q*,dj)= /dot product 4、example（略） 注： r的确定可以看|A-Ar|F 是否满足门限要求，但要得到最优的LSI性能，is an open questions. 但在给定r的情况下，Ar是最好的近似。,Text retrieval Technology(续),评价IR方法的效率 Recall(召回率)=相关文档数/总相关文档数 Precision(准确率)=相关数/查询返回总数 How to calculate? 采用人工建立测试集的方法。,Text retrie
9、val Technology(续),Recapitulation 1、文本检索任务&过程 2、Retrieval model(BoolM,VSM,LSI) 3、评价IR方法的效率,P2P technology,1、Overlay Network 2、What is P2P Computing 3、P2P Networks 有址型、无址型 4、P2P Applications File Sharing, File Storage, etc.,1、Overlay Network,Network 需要考虑：locating(名址）, routing, 网络拓扑三大问题 Overlay Network
10、 基于若干个现存网络构建 构成一个虚拟的层 解决或缓解底层网络的一些问题。,1、Overlay Network (cont.),Internet is an overlay network 互连各种网络（目标） 底层网络可以是以太,令牌, etc. 得到一个IP层 Benefits 不必修改现存的协议，可能需要为新的层构造协议。 不是每个节点任何时候都需要overlay network服务,1、Overlay Network (cont.),Disadvantages 增添负载（多了一个层，有些功能可能重复如：48bits地址 & 32bits地址）和层次增多必然带来交互的复杂性。 注： 因为
11、应用目标需求，而建立overlay network, 当然修改现存网络使之适应目标需求也是可行的。例：要实现网络互联。One ON per App? P2P network is overlay network! Can overlay IP网络 or 实际网络 or ？YES! 自然三大问题存在。,2、What is P2P computing,两节点，进行资源的共享、通信，使用尽可能少的中心控制。这样的计算模式相比于c/s计算，称为p2p计算（对等计算）。节点称为Peer. 为实现某一应用目标，若干peer互连形成一个overlay network, 节点间以p2p方式交互。称为：p2p
12、overlay network,简称p2p network. 例：Gnutella,Tapstry.,What (C/S vs. P2P (cont.),What (C/S vs. P2P (cont.),3、P2P Networks,按照对三问题的考虑是否引入 P2P网络层地址(ONLA)分： 有址型P2P network Peer节点有特设的ONLA地址 无址型P2P network Peer节点没有特设的ONLA地址,有址型 P2P network,Plaxton,Tapestry,Pastry,CAN,Chord,etc. 1.locating e.g. ONLA(Peer)=SHA-
13、1(Peers IP) 160bit ONLA地址空间；128bit 对象地址空间 Locating函数就是两空间的确定性映射。 2.Routing problem(how get to target?) 要是知道目标IP,利用IP层路由算法，不就可以到达目标？类DNS,RAP协议？反函数？,有址型 (cont.),不“直接”利用IP层路由算法，构建自己的p2p网络路由算法！ 以Plaxton为例。 数据结构： ONLA=0x4444的 Peer节点路由 (邻居)表,有址型 (cont.),最长前缀路由算法（类CIDR）： 假定要从0x32F8节点到0x4444. 0x32F8的节点在自己路由
14、表中第一列查找以4开头的地址，假定是4987。然后4987节点在其路由表第二列查找以44开头的地址，假定是4467。类推。 即：3278-4xxx-44xx-444x-4444 路由表大小及路由长度：O(logN),有址型 (cont.),节点加入与离去，路由表构造算法等略。 Tapestry,Pastry思想承Plaxton，对节点加入与离去及路由表结构及维护稍有区别。 Chord、CAN（omited）,无址型 P2P network,NapsterS,GnutellaS,FreenetS, etc. 1.没有特设ONLA 2.邻居路由表存放IP,按底层IP路由算法到达目标节点。,Naps
15、ter network,中心目录服务器 Locating(o)=? Routing=? 系统结构存在单点 失效问题，可扩展 性差,面对单点失效,设置多个中心 自我为中心 (O(log2n),O(n2log2n) 两个极端的折衷：Gnutella, Tapstry,etc.,?,Gnutella Network,1,2,3,4,5,6,7,Steps: Node 2 initiates search for 对象A 注：根本就不知道A在哪里，只好 Flooding.,Gnutella Network,1,2,3,4,5,6,7,Steps: Node 2 initiates search for
16、 对象A Sends message to all neighbors,Gnutella Network,1,2,3,4,5,6,7,Steps: Node 2 initiates search for 对象A Sends message to all neighbors Neighbors forward message,Gnutella Network,1,2,3,4,5,6,7,Steps: Node 2 initiates search for A Sends message to all neighbors Neighbors forward message Nodes that have对
