分布式RDF关键词近似搜索方法

现有的RDF关键词搜索方法主要是在大规模的RDF数据图上直接进行搜索,未能充分利用RDF本体中的语义信息,迭代次数过多造成搜索效率和效果不理想.针对这些问题,借助Redis内存数据库集群,提出分布式RDF关键词近似搜索算法(DKASR),即在分布式平台上实现大规模数据的并行搜索.算法结合RDF本体的语义信息构建本体子图,利用语义评分函数对本体子图进行排序,借助MapReduce计算模型实现并行搜索并返回Top-k结果;如果返回的结果没有达到Top-k,则对本体子图进行扩展生成近似本体子图,使用语义相似度函数对近似本体子图进行排序,再利用MapReduce计算模型实现并行搜索,直到返回Top-k结果.实验结果表明,DKASR算法能够高效正确地实现RDF关键词近似搜索并有效返回Top-k结果.     

基于关键词的RDF数据查询方法

在建立关键词倒排索引和路径索引的基础上,提出一个利用量化均衡规则和等距规则的启发式查询算法,并按照查询结果的大小排序返回最相关的前k个结果.通过建模RDF数据为RDF句子图,将文本信息封装到句子节点,同时将查询结果建模为包括所有查询关键词并且叶节点是关键词节点的无根树,将关键词查询问题转化为斯坦纳树问题.假设RDF句子图包括n个节点,最坏情况下索引占用的空间是3n2.假设关键词节点数为k,查询算法的时间复杂度为O(kn).该方法不需要依赖RDF数据的模式信息,支持对数据中的属性和关系名进行关键词查询.实验证明该方法能够快速而有效地实现RDF数据的关键词查询.     

基于压缩实体摘要图的RDF数据关键词查询

提出一种将关键词查询转换为SPARQL查询的方法来进行RDF数据的搜索.首先,根据RDF本身的关联特点,构建一个压缩实体摘要图;然后,借助关键词与所在实体的索引,将所查询的关键词在该摘要图上进行定位,通过图双向搜索算法找出包含关键词实体的前k子图,获得查询实体之间的关系,再联合最初的关键词及他们的属性,构建SPARQL查询;最后使用SPARQL搜索引擎执行查询.实验结果表明,所提方法较其他方法有更快的响应时间及更高的准确率.     

大规模图数据的正则路径查询

提出一种基于大规模RDF查询引擎gStore的分而治之方法, 对查询的正则表达式进行划分。在对定长字符串预处理的基础上, 再处理带有通配符的即时路径查询。该方法能够在开始阶段对搜索空间进行大量剪枝, 可以提高查询性能, 还能很好地解决正则表达式在RDF图中的路径匹配问题, 保证了对大规模图数据的支持。在DBpedia和LUBM上的实验表明, 该方法能够平均在秒级时间内返回路径查询结果。     

基于本体的XML数据源语义集成研究

提议了一个基于本体的XML数据源语义集成方法,为每个参与集成的XML文档产生一个局部RDF本体,合并局部本体的结果产生一个全局本体.全局本体统一查询访问并在后台局部XML数据源之间建立语义关系,在全局本体上的查询通过从RDF查询到XML查询的转换被处理.     

基于图模型的RDF/RDFS本体抽取方法

为了提高RDF/RDFS本体中特定领域知识的利用效率,提出了一种从源本体中抽取出特定领域本体的算法.将RDF/RDFS本体抽象为图模型;根据RDFS推理规则生成RDFS本体图模型的闭包;应用图理论构建抽取算法,生成以特定领域术语词典中概念为节点的子图,得到所需的领域本体.抽取结果表明,该方法对于RDF层次的领域本体抽取有良好的适用性,可快速有效地构建特定领域本体.     

一种基于Hadoop的大规模图最短路径查询方法

图的最短路径查询作为图论的经典问题,广泛应用于现实世界的许多应用中.然而随着图的规模日益增大,传统单机环境下的查询算法已无法满足大规模图的处理需求.为解决上述问题,提出基于Hadoop的大规模图最短路径查询方法(D-CH方法):首先利用经典的图分割算法(CNM算法)将存储于Hadoop分布式文件系统(HDFS)中的大规模图进行分割,给出了适于后续算法的标记分割结果;然后将查询区分为分割后子图内查询和子图间查询,基于MapReduce编程模型分别给出相应的并行化查询处理算法.实验结果表明,D-CH方法对大规模图的最短路径查询具有良好的执行效率.     

一种基于向量空间模型的Web本体自动分类方法

在分析了Web本体的结构特征和语言学特征基础上,引入虚拟文档的概念,定义整个本体的虚拟文档为与主题相关的vocabularies的虚拟文档的组合.以虚拟文档中的词条作为Web本体分类的特征项.基于RDF图不容忽视的图状特性,在构造自RDF图本体的词汇依赖图(vocabulary dependency graph)之上采用相关基于图的排序算法,得到与构造本体虚拟文档相关的vocabularies对于该本体的重要性权值,进而计算特征项的权值.     

分布式Top-k子图匹配技术

Top-k子图匹配是一种应用广泛的图搜索技术。相比于单机环境,分布式环境下的Top-k子图匹配问题具有更大的挑战性。该文分析了已有方法在分布式环境下存在的问题,提出了包括查询拆分、查询执行、结果连接3个步骤的算法。算法通过查询拆分,彻底避免了生成中间结果过程中的数据传输,同时通过优化查询执行和结果连接步骤,避免不必要的中间结果生成,降低单个节点的计算量,提升整体效率。在此基础上,该文对分布式环境下Top-k连接策略进行了进一步优化。在真实图数据上进行的实验测试表明:该文提出的算法能够有效解决分布式环境下Top-k子图匹配问题,具有很好的扩展性,而且使用优化连接策略的算法性能较基础算法的效率有明显的提升。     

支持增量图数据的超图查询算法研究

当前大部分图查询算法都是针对静态图数据,不适用于现实应用中不断更新的图数据。针对这一问题,提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果,算法在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算。通过分析证明,所提算法时间和空间复杂度不随数据图的增加而呈线性增长,节省了大量时间和空间代价。     

基于本体和局部查询反馈的微博查询扩展算法

传统的基于关键词匹配的查询方法因查询词短少,微博博文短小,容易引起歧义性,对查询效率有较大影响.提出一种基于本体和局部查询反馈的微博查询扩展算法,首先结合安全领域文档构建安全领域本体知识库,然后利用本体提供的语义知识对初始查询词进行扩展,再结合局部查询反馈对候选扩展词集进行筛选,最后通过二次查询和迭代操作得到最终查询结果.实验结果表明,基于本体和局部查询反馈的微博查询扩展算法比基于关键词的查询扩展算法、基于本体的查询扩展算法和基于"伪相关反馈"的查询扩展算法有更好的查全率和查准率.     

具有结果多样性的近似子图查询算法

针对大型图中的各种top-k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题,提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引,并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中,利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集,并从不同区域找到多个满足要求的近似匹配子图,避免了查询结果间的高重复率.同时,基于区域和同标号近邻簇的划分,优先查找属于不同划分或不同簇顶点的匹配,减少了不同区域划分间的交互,提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.     

基于RDF的海量语义数据管理研究

随着Web信息呈指数级增加,目前存储模式已难以适应大规模RDF数据高效存储的需求。本文通过对语义万维网结构以及RDF语义文件存储和查询技术的研究,分析了海量语义数据管理的研究领域和现状,提出了基于RDF的海量数据管理框架。该框架旨在实现对海量数据的管理,以解决RDF数据管理中存在存储设计难度大,查询处理复杂且效率低,查询结果排序困难的问题。     

基于HITS算法的查询结果多样化方法

现有的查询结果多样化研究很难准确得到用户多样性需求并提供与用户查询各个方面需求相关的文档。针对这个问题,本文基于HITS算法的网页间链接分析特性,根据网页链接图直接计算查询结果列表中的文档可能满足用户多样性需求的程度,并将其应用到结果列表的重排序中以实现搜索结果多样性。在TREC大规模数据集合上的实验结果表明了该方法的有效性。     

求解服务选取问题的混合蚁群优化算法

为解决大规模服务选取问题,提出了一种混合蚁群优化(HACO)算法.该算法先采用动态skyline服务查询过程过滤抽象服务类相关的冗余候选服务,以大力缩减空间提高查找效率,然后利用聚类设计动态构造图来引导蚂蚁的搜索方向,从而确定局部服务选取的搜索区域;基于已经确定的局部服务选取的搜索区域,利用启发式策略选取具体的组合服务.采用标准的真实数据集和综合产生的数据集对所提的方法进行试验评估,以及和最近提出的相关组合服务算法进行对比.实验结果在解的质量和处理时间方面效果显著.     

基于领域本体的信息搜索模型

针对目前的搜索模型局限于语法层次上关键词匹配的特点,以领域本体作为知识组织方式,提出了一种语义环境下基于本体的信息搜索模型.在此模型的基础上,分别提出了文档语义标注算法和搜索词语义扩展算法,两种算法分别对文档集语义分析和搜索词语义关系理解,实现双向语义信息搜索的目的.实验结果表明,提出的信息搜索方法能够克服关键词匹配搜索的不足,获得较好的搜索效果     

CPU-GPU异构环境下的大规模商品知识查询处理

知识图谱是将无结构的知识进行结构化表示和组织的有效途径,已经成为支持众多智能应用的基础设施.然而,与商品相关的知识通常呈现出海量性、异质性和层次性的特点,这对现有基于关系模型和图模型的知识查询处理方法提出了挑战.针对商品知识的这些特点,本文设计与实现了一种利用CPU和GPU协同计算的商品知识查询处理方法.首先,为了充分发挥GPU的并行计算能力,提出了一种基于稀疏矩阵的商品知识存储策略,并针对商品知识进行存储优化;其次,根据稀疏矩阵的存储结构设计了一种查询转换方式,将SPARQL查询转化为对应的矩阵计算,并将连接查询算法扩展到GPU上进行加速.为了验证所提出方法的有效性,我们在LUBM数据集和一个半合成的商品数据集上进行了一系列的实验.结果表明,本文提出的方法,不仅在海量商品知识下相对于现有RDF查询引擎在检索效率上有较大提升,而且在通用的RDF标准数据集上也能取得较好的检索性能,并验证了GPU加速查询处理的有效性.