基于语义的Double-Circle-DHT搜索技术的研究.ppt

基于语义的Double-Circle-DHT
搜索技术的研究
网络中心研究生刘杰
2009年7月
基于语义的Double-Circle-DHT
搜索技术的研究
简介
的快速发展,由于P2P具备可扩展性、健壮性、对等的结构等优点,P2P被越来越多地应用到互联网资源共享中,P2P网络经过近十年的发展,已经从第一代的中心索引拓扑和第二代的无结构式拓扑结构发展到了现今广泛采用的结构化P2P(如Chord 、Tapestry 、CAN 、Pastry等),而他们都基于DHT(Distributed Hash Table)技术,其优点是可以保证在一定的跳跃次数内查找到P2P网络中存在的数据对象,但只能根据资源的键值(关键字)进行准确匹配的查询,从目前的应用上来
基于语义的Double-Circle-DHT
搜索技术的研究
看,P2P网络主要体现在大范围的共享、搜索的优势上。如何在用户广泛分布、数量巨大、节点行为不可控、计算能力和网络连接不均匀的复杂环境下实现高效的搜索服务是P2P应用面临的巨大挑战。
因此本文提出一种基于语义划分的双环分布式散列表(Double-Circle-DHT)搜索算法,在Chord环的基础上增加一个基于语义相似角排列的语义环,首先通过Chord算法进行精确查找,当精确查找无法命中时将查询转入语义环通过语义相似角进行模糊匹配并返回语义相似角最接近θ的n个节点(其中n为设定的阀值)。从而实现精确查找和模糊匹配的融合,提高查全率。
基于语义的Double-Circle-DHT
搜索技术的研究
算法基本思想
通过向量空间模型(VSM)提取资源文档的文档向量,计算出语义相似角,再通过Hash算法生成节点资源的唯一标识<key, value>,从而生成唯一标识一个节点的序列<key, value,θ>,将已有节点按照Chord环排列,同时每个节点保存m个语义相似角最接近自己的节点标识序列。当查询请求到达时先按照Chord算法进行精确查找,当精确查找无匹配结果时,由最后执行精确查找的节点将请求发送给语义相似角最接近请求节点语义相似角的节点,直到进行到当前节点语义
基于语义的Double-Circle-DHT
搜索技术的研究
相似角与请求节点的语义相似角差值比指针表中任一节点语义相似角与请求节点语义相似角差值都小时为止,并返回语义相似角最接近的n个节点(n为设定的阀值)的标识序列。
算法的实现
1、节点资源的提取
(1)利用VSM模型表示节点资源文档,通过TDIDF技术得到节点资源文档相应的文档向量V,并计算出语义相似角。其中向量空间模型(VSM)是信息获取领域经典的统计算法,它将描述文档的多个特征词以向量的形式来表示,向量中的每
基于语义的Double-Circle-DHT
搜索技术的研究
个分量对应了文档的不同特征。用户进行文档搜索时,将提交的描述文档的多个特征词也用类似的向量表示,通过比较两个向量的相似程度来进行文档的匹配。假设整个P2P网络中包含的文档集合为D,D由N个不同的文档构成,即D={d1,d2,…dn,}。D中所有文档的特征构成了特征集合F,F包含m个特征,即F={f1,f2,…,fm}。文档∈R可以用向量表示为di=(,f2,…,fm),其中W(i,(1≤j≤m)为文档的第j个特征的数值表示。它的最简单表示是采用二值表示,即当文档包含特征时,为1,否则为0。二值表示简单,计算量小,但是不能准确地表达不同特征对文档的重要程度,而利用
基于语义的Double-Circle-DHT
搜索技术的研究
TDIDF技术可以很好的解决上述问题,准确地建立起文档的空间向量模型,将文本表示城向量的形式。其中,TF表示在某文档中某特征词出现的数量,DF表示该文档集中拥有该特征词的文档数量,TF值除以DF值就是该特征词对应的TFIDF值。因此可以定义文档相似角为:

给定任何一个文档向量,都可以由该公式计算出该文档向量与单位向量比较而得出的相似角。
基于语义的Double-Circle-DHT
搜索技术的研究
(2)根据Chord算法计算出节点的关键字标识key和节点标识value。
(3)由以上两个步骤可得出唯一标识一个节点的序列<key, value,θ>。
2、节点资源的发布和搜索
节点资源的发布过程如下:
(1)首先生成能够唯一标识节点的序列<key, value, θ>,在Chord环中找到合适的位置加入。
(2)查询Chord环中各节点语义相似角,并将语义相似角最接近的m个节点加入指针列表。
基于语义的Double-Circle-DHT
搜索技术的研究
节点的搜索过程如下:
(1)节点收到查询请求时利用Chord算法进行精确查找。
(2)当精确查找结果不存在时,由当前节点执行