Worst-Case-Optimal Joins on Graphs with Topological Relations

Spatial data play an important role in many applications built over knowledge graphs, and are frequently referenced in queries posed to public query services, such as that of Wikidata. Querying for spatial data presents a significant challenge, as topological relations such as adjacent or contains imply inferred information, such as through the transitivity of the containment relation. However, despite all the recent advances in querying knowledge graphs, we still lack techniques specifically tailored for topological information. Applications looking to incorporate topological relations must either materialize the inferred relations, incurring high space and maintenance overheads, or query them with less efficient recursive algorithms, incurring high runtime overheads. In this paper we address the problem of leveraging topological information in knowledge graphs by designing efficient algorithms to process these queries. Our solution involves building a specific index that stores the topological information in a convenient compact form, and includes specialized algorithms that infer every possible relation from the basic topological facts in the graph. We show that, while using essentially the same space required to solve standard graph pattern queries, we can incorporate topological predicates, accounting for all the inferred information, all within worst-case-optimal time. We implement our scheme and show experimentally that it outperforms baseline solutions by a notable margin.