Querying Web-Scale Knowledge Graphs Through Effective Pruning of Search Space
Querying Web-Scale Knowledge Graphs Through Effective Pruning of Search Space
复制标题
通过有效修剪搜索空间查询网络规模的知识图
DOI：
10.1109/tpds.2017.2665478
复制
发表时间：
2017-08-01
影响因子：
5.3
通讯作者：
Gao, Lixin
中科院分区：
文献类型：
--
作者：
Jin, Jiahui;Luo, Junzhou;Gao, Lixin
如今，包含数十亿实体的网络规模知识图很常见。查询这些图可以建模为一个子图匹配问题。由于知识图本质上是不完整和嘈杂的，因此发现与查询完全匹配的答案以及与查询相似的答案非常重要。现有的图匹配算法通常使用图索引来加速查询处理。对于十亿节点图，由于工作量和所需的内存/存储，构建图索引可能是不可行的。在本文中，我们提出了一个有效的算法，找到最好的<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><inline-graphic xlink:href="jin-ieq1-2665478.gif"/></alternatives></inline-formula>答案，对于一个给定的查询，而无需预先计算图索引。答案的质量是通过在线计算的匹配分数来衡量的。为了加速查询处理，我们提出了一种新的技术，在计算过程中的匹配分数的边界。通过使用边界，可以有效地修剪低质量的答案。边界技术可以在分布式环境中实现，使我们的方法能够有效地查询网络规模的知识图。我们评估了我们的方法在真实世界数据集上的有效性和效率。结果表明，我们的边界技术可以减少运行时间的两个数量级相比，不使用边界的方法。
Web-scale knowledge graphs containing billions of entities are common nowadays. Querying these graphs can be modeled as a subgraph matching problem. Since knowledge graphs are incomplete and noisy in nature, it is important to discover answers matching exactly as well as answers similar to queries. Existing graph matching algorithms usually use graph indices to accelerate query processing. For billion-node graphs, it may be infeasible to build the graph indices due to the amount of work and the memory/storage required. In this paper, we propose an efficient algorithm for finding the best <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives> <inline-graphic xlink:href="jin-ieq1-2665478.gif"/></alternatives></inline-formula> answers for a given query without precomputing graph indices. An answer’s quality is measured by a matching score that is computed online. To accelerate query processing, we propose a novel technique for bounding the matching scores during the computation. By using bounds, the low quality answers can be efficiently pruned. The bounding technique can be implemented in a distributed environment, allowing our approach to efficiently query web-scale knowledge graphs. We evaluate the effectiveness and the efficiency of our approach on real-world datasets. The result shows that our bounding technique can reduce the running time up to two orders of magnitude comparing to an approach without using bounds.