广域P2P知识共享和检索系统研究.pptx

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 如何表达需要的信息？自然语言？词，如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个词，每个词在文档中的权重 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 retrieval 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|)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 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 Document 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 questions.但在给定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 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 不必修改现存的协议，可能需要为新的层构造协议。不是每个节点任何时候都需要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两节点，进行资源的共享、通信，使用尽可能少的中心控制。这样的计算模式相比于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 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为例。数据结构：ONLA=0 x4444的 Peer节点路由 (邻居)表 0XXX40XX440X44401XXX41XX441X44412XXX42XX442X44423XXX43XX443X44434XXX44XX444X44445XXX45XX445X44456XXX46XX446X4446有址型(cont.)最长前缀路由算法（类CIDR）：假定要从0 x32F8节点到0 x4444.0 x32F8的节点在自己路由表中第一列查找以4开头的地址，假定是4987。然后4987节点在其路由表第二列查找以44开头的地址，假定是4467。类推。即：3278-4xxx-44xx-444x-4444路由表大小及路由长度：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(n2log2n)n两个极端的折衷：Gnutella,Tapstry,etc.?Gnutella Network1234567ASteps:1.Node 2 initiates search for 对象A注：根本就不知道A在哪里，只好Flooding.Gnutella Network1234567ASteps:1.Node 2 initiates search for 对象A2.Sends message to all neighborsAAGnutella Network1234567ASteps:1.Node 2 initiates search for 对象A2.Sends message to all neighbors3.Neighbors forward messageAAAGnutella Network1234567Steps:1.Node 2 initiates search for A2.Sends message to all neighbors3.Neighbors forward message4.Nodes that have对象A initiate a reply messageA:5AA:7AAGnutella Network1234567Steps:1.Node 2 initiates search for A2.Sends message to all neighbors3.Neighbors forward message4.Nodes that have对象A initiate a reply message5.Query reply message is back-propagatedA:5A:7AAGnutella Network1234567Steps:1.Node 2 initiates search for A2.Sends message to all neighbors3.Neighbors forward message4.Nodes that have对象A initiate a reply message5.Query reply message is back-propagated6.Node 2 gets repliesA:5A:7Gnutella Network1234567Steps:1.Node 2 initiates search for A2.Sends message to all neighbors3.Neighbors forward message4.Nodes that have对象A initiate a reply message5.Query reply message is back-propagated6.Node 2 gets replies7.File downloaddownload AFreenet networkn逐步趋向目标，可能会误导Freenet networknSamll world model&Freenet networknStanley Milgram 1960s 实验 在美国，互不相识的两人，若存在熟人链的话，其平均链长5-6。实验表明：短链普遍存在并且人们能自主地发现它们（没有全局的知识）。此即小世界现象，又称“six degrees of separation”principle。Small World&Freenet为小世界现象建模nModel 1:Pool and Kochen Model 每个节点均匀随机地从所有其它节点中，选择少量的节点连边（相识对称）。nModel 2:Watts&Strogatz Model(Nature98)相识边分两种。大量的local边（近邻），少量的long-range边（远亲）。远亲从远节点中均匀随机选择。Small World&FreenetnModel 3:Jon Kleinberg(Nature00)泛化model 2。选择远亲时，与离该节点的曼哈顿距离d有关，以概率d-r连边。在model2意义下，r=0。Th2:在Grid中，r=2是最优值。非集中式算法产生链长上界o(log2n)Th3:当r=2,p=q=1,算法A链长上界o(log2n)离节点距离p内的节点均为近邻。q为远亲数。A:选择最接近目标的邻居转发Small World&FreenetModel 3 图示：Small World&Freenet评:以small world model组织网络Freenet一维地址空间，主要依据模型2无址型网络路由算法改进n略4、P2P applicationsn分为三类：硬件资源的共享：如SETHOME,空闲cpu 周期共享协同计算和通信：如Groove,地理上分散的小组成员间协同交互信息资源的共享：如p2p搜索引擎。4、P2P applicationsnFile StoragenFile SharingnP2P Search Enginenapplication-layer multicast,event notification services,and peer-to-peer web caching,etc.(略)File Storage ApplicationnOceanStore,Past,etc.1.SHA-1(key(file)将文件哈希到peer节点的地址空间或子空间中，实现key(file)到peer节点的映射。路由该文件（位置）信息到相应的peer节点上（named as 责任节点、根节点）。一节点负责维护若干文件（位置）信息。2.对某文件的请求，采用SHA-1(key(file)获取其责任peer节点地址，再利用底层路由算法到达该节点。得到文件实际存放的位置或就是文件本身。File Sharing ApplicationsnNapster,Gnutella,Freenet,etc.如何定位对象（file）？1.存在集中式目录服务器 Napster-like 2.flooding(broadcast)算法(宽度优先搜索)Gnutella-like 3.深度优先搜索算法 Freenet-likeFreenet Sharing ApplicationsnDistributed file sharing systemnCompletely anonymous for producers or consumers of informationn文件存储的授权访问nKey=hash(file content)Evaluation for Gnutella.nPeer is not equalnPower-law network model?nMost of peers uptimes are no more than two daysn30%vs.70%Evaluation for GnutellanThe overlay network topology doesnt match the underlying Internet infrastructure topology!40%of all nodes are in the 10 largest Autonomous Systems(AS)Only 2-4%of all TCP connections link nodes within the same ASLargely random wiring Organize the overlay network to match the underlying infrastructure topology?小节nOverlay networknP2p computing conceptnP2p network&main issuesnP2p applicationnEvaluation for file sharing system小心地说nCAN,Chord,Pastry,Tapstry only supports “exact search”!为了可靠性、可用性、性能、qos,存在系统管理负担nGnutella Supports“Partial-match search”易建立，来去自由。能否获得好的qos?nTornado支持？nRetrieval Vs.Search研究动机nMotivation1 人们经常从互联网上下载自我有用的信息（可能是静/动态web页面、学术论文、mp3、rm等,称为知识）到桌面机上。日积月累，这些信息的管理和再提取（重新找回来）成为问题。(?)研究动机n可能的解决 1.构造一个语义文件系统，支持基于文件内容的检索?其实现在的文件系统如windows,正是在这方面不断努力，但是仍存在找不到的情况。而且需要为每种文本类型构造相应的处理程序。(有些pdf文件为何不允许基于内容检索？)研究动机n可能的解决 2.再次光顾互连网？a、通过搜索引擎查找；b、直接给出要找对象URL/URN。看看可能发生的情况：1、搜索引擎和原来的web站点存在单点失效问题,比如：停止提供服务、站点永久或临时关闭、网络分隔、所要信息已经被更新或删除等；2、即使单点失效问题不会发生，为了得到该信息，我们必须承受较大的网络延迟和浪费不必要的网络带宽资源。然而我们需要的就在我们的机器里。研究动机nMotivation2 用户通常处于一个网络社区中（如LAN,校园网）。当用户需要同样的信息时，都是独立地到社区外去查找,浪费了带宽资源(对于ISP来说，尤为考虑)。可以考虑首先在社区内查找，若找不到，才到社区外或ISP为社区建立常用信息存储？-应该是动态构建，而非类似FTP服务器一样的人为构建与维护。1、我们需要的通常在我们的周围都能找到？2、对“以web为中心的数据访问模式变为真正的分布式数据访问模式”作了贡献？研究动机n很自然地，需要这么一个便利的工具 1.既能从互联网上浏览、下载信息，同时也能有效的组织管理这些下载来的信息，并提供事后基于内容的再次提取。2.这些知识通过P2P网络组织起来便可以提供广域的共享。同时，许多动态页面(通过传统搜索引擎不能检索到的)也出现在这个网络中。n两个研究点“捆绑”到一个应用系统中来，给用户的感觉更多地象一个搜索引擎。谢谢！