Zooming out on an evolving graph

Amir Aghasadeghi, Vera Z. Moffitt, Sebastian Schelter, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationAdvances in Database Technology - EDBT 2020
    Subtitle of host publication23rd International Conference on Extending Database Technology, Proceedings
    EditorsAngela Bonifati, Yongluan Zhou, Marcos Antonio Vaz Salles, Alexander Bohm, Dan Olteanu, George Fletcher, Arijit Khan, Bin Yang
    PublisherOpenProceedings.org
    Pages25-36
    Number of pages12
    ISBN (Electronic)9783893180837
    DOIs
    StatePublished - 2020
    Event23rd International Conference on Extending Database Technology, EDBT 2020 - Copenhagen, Denmark
    Duration: Mar 30 2020Apr 2 2020

    Publication series

    NameAdvances in Database Technology - EDBT
    Volume2020-March
    ISSN (Electronic)2367-2005

    Conference

    Conference23rd International Conference on Extending Database Technology, EDBT 2020
    CountryDenmark
    CityCopenhagen
    Period3/30/204/2/20

    ASJC Scopus subject areas

    • Information Systems
    • Software
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'Zooming out on an evolving graph'. Together they form a unique fingerprint.

    Cite this