实验室动态

[2017 CIKM] Keyword Search on RDF Graphs — A Query Graph Assembly Approach

韩硕关于使用图拼接方法来进行RDF图上关键字查询的论文(Keyword Search on RDF Graphs — A Query Graph Assembly Approach)被 CIKM 2017 录用。

关键词检索为普通用户提供了一种简单易用的查询RDF数据的方式。本文的研究内容是如何将用户输入的关键词查询序列,高效地转化为一张能够准确表达用户查询意图的查询图。基于用户输入的关键词序列,我们首先将其划分标注为若干个语义单元,映射到一些查询图构建元素上,即一些实体/类别顶点和关系边。然后我们形式化地定义了查询图拼接(QGA)问题。我们在理论上证明了 QGA 问题是 NP 完全的。尽管如此,我们提出了一个基于二部图匹配模型的最佳优先搜索算法,并设计了一些启发式的剪枝下界。这一算法的时间复杂度并不依赖于 RDF 图的规模,从而保证了我们的系统具有良好的可扩展性,能够高效地应对真实的大规模 RDF 数据。