Online Indices for Predictive Top-k Entity and Aggregate Queries on Knowledge Graphs
Online Indices for Predictive Top-k Entity and Aggregate Queries on Knowledge Graphs
复制标题
DOI：
10.1109/icde48307.2020.00096
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Yan Li;Tingjian Ge;Cindy X. Chen
中科院分区：
文献类型：
--
作者：
Yan Li;Tingjian Ge;Cindy X. Chen
知识图谱的应用越来越广泛。然而，据了解，它们是不完整的。我们定义了虚拟知识图的概念，它扩展了具有预测边缘及其概率的知识图。我们专注于两种重要类型的查询：top-k实体查询和聚合查询。为了提高查询处理效率，我们提出了一个增量索引的低维实体向量转换从网络嵌入向量。我们还设计了查询处理算法的索引。此外，我们提供了理论保证的准确性，并进行了系统的实验评估。实验结果表明，该方法是非常有效的。特别是，与相同或更好的精度保证，它是一个到两个数量级的查询处理速度比最近的以前的工作，只能处理一个关系类型。
Knowledge graphs have seen increasingly broad applications. However, they are known to be incomplete. We define the notion of a virtual knowledge graph which extends a knowledge graph with predicted edges and their probabilities. We focus on two important types of queries: top-k entity queries and aggregate queries. To improve query processing efficiency, we propose an incremental index on top of low dimensional entity vectors transformed from network embedding vectors. We also devise query processing algorithms with the index. Moreover, we provide theoretical guarantees of accuracy, and conduct a systematic experimental evaluation. The experiments show that our approach is very efficient and effective. In particular, with the same or better accuracy guarantees, it is one to two orders of magnitude faster in query processing than the closest previous work which can only handle one relationship type.