SparkHINlog: Extension of SparkDatalog for heterogeneous information network

Abstract

Real world data is often interconnected, forming large and complex heterogeneous information networks (HINs) with multiple types of objects and links such as bibliographic network (DBLP) and knowledge bases (YaGo). Querying meta-paths requires exploration of path instances which can be computational cost in large HINs. However, existing meta-path based studies mostly focus on analytical applications of meta-paths, rather than systems to query meta-paths efficiently in large HINs. To bridge this gap, in this work we present SparkHINlog, a system based on Apache Spark, to handle meta-paths queries efficiently on large scale HINs. In SparkHINlog we propose an algorithm to not only translate meta-paths to Datalog rules, but also to manage the working memory area of Datalog efficiently to increase the scalability of SparkHINlog. To avoid the computing overhead of join operation to discover path instances when evaluating these rules, we leverage Motif Finding, a powerful tool of GraphFrames Library. With motif finding, SparkHINLog can speed up the time to evaluate the rules by path finding on graph instead on joining two relations. We conduct experimental comparisons with SparkDatalog, the state-of-the-art large-scale Datalog system, and verify the efficacy and effectiveness of our system in supporting meta-path queries.