Distance computation is a bottleneck that limits the performance of many applications based on knowledge graphs (KGs). One common approach to improving online distance computation is to offline precompute certain information to be stored in an index called distance oracle. However, its effectiveness remains under-studied in the setting where edges are methodologically weighted to capture the structure and semantics of edge types in a KG. To fill the gap, in this paper, we present the first evaluation of representative distance oracles on KGs with commonly used edge weighting schemes. Our negative results and empirical justifications provide insights and a motivation for future studies of this unique setting.

The Diameter-bounded max-Coverage Group Steiner Tree (DCGST) problem has recently been proposed as an expressive way of formulating keyword-based search and exploration of knowledge graphs. It aims at finding a diameter-bounded tree which covers the most given groups of vertices and has the minimum weight. In contrast to its specialization—the classic Group Steiner Tree (GST) problem which has been extensively studied, the emerging DCGST problem still lacks an efficient algorithm. In this paper, we propose Cba, the first approximation algorithm for the DCGST problem, and we prove its worst-case approximation ratio. Furthermore, we incorporate a best-first search strategy with two pruning methods into PrunedCBA, an improved approximation algorithm. Our extensive experiments on real and synthetic graphs demonstrate the effectiveness and efficiency of PrunedCBA.