【作者】 王丽娟；

【导师】 王国仁；

【作者基本信息】 东北大学 ， 计算机应用技术， 2013， 硕士

【摘要】 资源描述框架(Resource Description Framework,简称RDF)是语义Web中所使用的基本标记语言,在知识的组织与管理和社会网络应用中广泛应用。RDF数据的规模随着语义Web应用的发展而增大。RDF数据具有典型的图特征,含有复杂的结构信息,以及大量的文本信息。可见,如何在大规模RDF数据上进行高效的关键词查询是当前研究的热点之一。针对已有研究在查询执行效率和结果质量方面存在的不足,提出了基于近似组斯坦纳树的大规模RDF数据关键词查询方法RAGS。RAGS将RDF上的关键词查询映射为组斯坦纳树问题,然后通过将组斯坦纳树问题规约为最小斯坦纳树问题进行求解。针对经典的最小斯坦纳树算法是非规约安全的问题,提出了改进方法,并分析了算法的时间复杂度和近似比性能。为了使大规模RDF数据上的关键词查询具有更友好的用户体验,设计了最短路径三元组倒排索引结构,通过离线预先计算全源最短路径的方式,改善在线查询的实时性；提出基于升序排列生成树算法的top-k查询方法,以便更快的为用户返回准确结果。考虑到对于大规模RDF数据而言,索引构建时间也是系统的主要瓶颈。提出基于整体同步并行计算模型(Bulk Synchronous Parallel,简称BSP)的全源最短路径分布式并行算法,加快索引的构建。实验显示,RAGS在时间性能和结果质量方面具有较好的性能,基于BSP的分布式算法具有较好的可伸缩性。更多还原

【Abstract】 RDF (Resource Description Framework) is the basic markup language used in the semantic Web, which has been widely applied in knowledge organizing and management, and social networks. The scale of RDF data increases rapidly as the growth of semantic Web applications. RDF data has a typical graph model, complex structures, as well as large amount of text information. Therefore, some studies focus on how to efficiently process keyword queries on RDF data. To improve the performance of query processing and the quality of query results in the existing related work, a novel keyword search approach on large scale RDF data,named RAGS, is proposed based on the solution of approximate group steiner tree problems.In RAGS, a keyword search on RDF data is translated to the problem solving of group Steiner tree. Then, the problem is solved by reducing the group Steiner tree problem to a minimum Steiner tree problem. For those traditional minimum Steiner tree approaches that are not safe for reduction, an improved approach is proposed and analyzed in its time complexity and approximate ratio.In order to make the keyword search approach more user friendly in the case of large scale RDF data, a shortest path triple inverted index is designed. It improves the performance of real-time online keyword search by pre-computing all pair shortest paths offline. Furthermore, a top-k search algorithm for rapid and accurate response to user queries is proposed based on generating spanning trees in increasing order cost.The time cost of the index construction is the primary bottleneck for large scale RDF data. Therefore, a BSP based distributed all pair shortest path algorithm is proposed to speed up the index construction.The experimental results show that RAGS has a better performance in response time and result qualities, and the distributed algorithm based on BSP also has a good scalability.更多还原