Portal: A Query Language for Evolving Graphs
Vera Zaychik Moffitt, Julia Stoyanovich · arXiv (Cornell University) · 2016
Graphs are used to represent a plethora of phenomena, from the Web and social networks, to biological pathways, to semantic knowledge bases. Arguably the most interesting and important questions one can ask about graphs have to do with their evolution. Which Web pages are showing an increasing popularity trend? How does influence propagate in social networks? How does knowledge evolve? Much research and engineering effort today goes into developing sophisticated graph analytics and their efficient implementations, both stand-alone and in scope of data processing platforms. Yet, systematic support for scalable querying and analytics over evolving graphs still lacks. In this paper we present Portal, a declarative language that supports efficient querying and exploratory analysis of evolving graphs, and an implementation of Portal in scope of Apache Spark, an open-source distributed data processing framework. Our language supports a variety of operations including temporal selection, join and aggregation, and a rich class of analytics. We develop multiple physical representations and partitioning strategies and study the trade-offs between structural and temporal locality. We provide an extensive experimental evaluation of our system, demonstrating that careful engineering can lead to good performance.