基于路径适配的大规模RDF数据子图匹配算法

摘要

子图查询与匹配是社会网络分析和大规模网络图知识发现中的核心技术,也是决定大规模社会网络分析和知识发现准确性的关键。针对当前大规模图数据环境下子图查询算法准确率低、开销大的问题,提出基于路径适配的子图匹配算法。首先基于路径建立图数据的RDF(Resource Description Framework,资源描述框架)索引;然后将查询子图分解为一组路径,在分解过程中为每条路径获得一组候选匹配路径;最后通过k-partition交集图将候选路径连接在一起,从而构建出查询图的结果子图。实验测试了在不同数据集上的路径索引构建时间以及F-measure值,与Spath(Shortest Path,最短路径)算法、Sapper算法和SQM(Subgraph Query Matching,子图查询匹配)算法相比,在处理大规模数据时,该算法的查询准确率提高了15%。