Bisimulation-based Structural Summaries of Large Graphs.

摘要

With an increasing number of heterogeneous entity descriptions available as large graphs that grow to millions of nodes and billions of edges, it is a challenge to understand, explore, and query these large graphs. Bisimulation-based structural summaries have often been used as a compact representation of the dataset that can improve query performance. However, current bisimulation summary construction techniques for large graphs do not scale and do not facilitate the use of summaries within existing systems. We address these challenges with three contributions. First, we describe bisimulation summary construction techniques for large graphs that leverage a novel singleton optimization which drastically reduces construction time. Second, we show how structural summaries can be used to improve query performance within existing RDF systems. Third, we give an ontology for describing structural summaries as RDF that enables their use and verification with existing RDF tools. Our work also demonstrates that the S+EPPs system, built on top of existing RDF processors, is an efficient, scalable, and flexible approach to exploring and querying large graphs using bisimulation-based structural summaries.