Weight Matters: An Empirical Investigation of Distance Oracles on Knowledge Graphs
Ke Zhang, Jiageng Chen, Zixian Huang, Gong Cheng · 2023
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.