一种基于可排序视图的RDF模式匹配算法

摘要：

随着语义网络中数据量的激增,在RDF数据集中高效查询数据已成为一个亟待解决的问题.传统的基于物化视图的RDF模式匹配方法虽然能降低表的自连接操作次数,加快查询模式重写过程,但在视图集中检索模式匹配的视图等价于子图同构这一NP-hard问题.为了减小查询模式重写代价,提高RDF模式匹配过程效率,引入可排序视图概念,设计包含映射发现算法contain及其扩展算法contain+,简化等长度模式间包含映射发现过程,同时保证模式间的匹配代价与输入数据的规模线性相关.此外,提出基于倒排表/MapReduce检索候选可排序视图的方法,实现RDF模式重写算法rewrite,用以处理不同规模数据集上的模式匹配问题.理论分析及实验证明,基于可排序视图的RDF模式匹配算法能有效地兼顾算法效率及算法可扩展性.

关键词：可排序视图、倒排表、Mapreduce、模式重写

所属期刊栏目：52

分类号：TP392(计算技术、计算机技术)

资助基金：国家自然科学基金60973023

在线出版日期：2016-08-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：62-69