TY - GEN
T1 - Zooming out on an evolving graph
AU - Aghasadeghi, Amir
AU - Moffitt, Vera Z.
AU - Schelter, Sebastian
AU - Stoyanovich, Julia
N1 - Funding Information:
∗This work was supported in part by NSF Grant No. 1916505.
PY - 2020
Y1 - 2020
N2 - An evolving graph maintains the history of changes of graph topology and attribute values over time. Such a graph has a specific temporal and structural resolution. It is often useful to modify this resolution during analysis, for example, to consider communities rather than individual nodes, or to quantify changes at the level of days rather than hours. We propose attribute-based zoom and temporal window-based zoom — two operators that support exploratory analysis of an evolving graph at different levels of resolution. We develop several alternative physical representations of an evolving property graph — a temporal generalization of a property graph — and detail how to implement the proposed zoom operators using dataflow operations. These different physical representations allow us to explore the trade-offs in temporal and structural locality with respect to the performance of the zoom operators. We implement the operators in Apache Spark, evaluate them on real evolving graph datasets, and demonstrate scalability to billion-edge graphs.
AB - An evolving graph maintains the history of changes of graph topology and attribute values over time. Such a graph has a specific temporal and structural resolution. It is often useful to modify this resolution during analysis, for example, to consider communities rather than individual nodes, or to quantify changes at the level of days rather than hours. We propose attribute-based zoom and temporal window-based zoom — two operators that support exploratory analysis of an evolving graph at different levels of resolution. We develop several alternative physical representations of an evolving property graph — a temporal generalization of a property graph — and detail how to implement the proposed zoom operators using dataflow operations. These different physical representations allow us to explore the trade-offs in temporal and structural locality with respect to the performance of the zoom operators. We implement the operators in Apache Spark, evaluate them on real evolving graph datasets, and demonstrate scalability to billion-edge graphs.
UR - http://www.scopus.com/inward/record.url?scp=85084183104&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85084183104&partnerID=8YFLogxK
U2 - 10.5441/002/edbt.2020.04
DO - 10.5441/002/edbt.2020.04
M3 - Conference contribution
AN - SCOPUS:85084183104
T3 - Advances in Database Technology - EDBT
SP - 25
EP - 36
BT - Advances in Database Technology - EDBT 2020
A2 - Bonifati, Angela
A2 - Zhou, Yongluan
A2 - Vaz Salles, Marcos Antonio
A2 - Bohm, Alexander
A2 - Olteanu, Dan
A2 - Fletcher, George
A2 - Khan, Arijit
A2 - Yang, Bin
PB - OpenProceedings.org
T2 - 23rd International Conference on Extending Database Technology, EDBT 2020
Y2 - 30 March 2020 through 2 April 2020
ER -