Tempura: A GraphX extension for temporal graphs in Apache Spark

Abstract

Data blir generert oftere og oftere. Økt datahastighet, -størrelse og -variasjon krever uttrykksfulle modeller og gode verktøy for en effektiv lagring og prosessering. Data blir ikke bare laget, men også oppdatert. Dette krever løsninger for å monitorere hvordan dataen endres for å gi en høyere forretningsverdi. Mange brukere av stordatasystemer holder ikke øye med hvordan data blir oppdatert, noe som minsker mulighetsrommet for analyse av historisk utvikling. Det er ingen standard på hvordan man skal modellere temporal data - data som endrer seg over tid. Selv om relasjonelle databaser er industristandarden for å lagre og prosessere data, kan dataen ofte bli modellert som en graf med noder og kanter. For å redusere kostnaden for å modellere temporal data introduserer vi Tempura. Tempura er et system for transformering og prosessering av temporal grafdata. På grunn av mangelen på tilgjengelige datasett som passer Tempura, så introduserer vi et rammeverk for å modifisere eksisterende grafdata. Vi utvider Apache Spark, og implementerer to lovende modeller fra tidligere arbeid på temporale grafdatastrukturer. Validity-modellen knytter tidsinterval til entiteter for å indikere når de er gyldige, og SnapshotDelta-modellen tar \textit{snapshots} på satte intervaller hvor endringene er lagret i \textit{deltaer}. Begge er implemenert bak et felles grensesnitt så API-et er modellagnostisk. Modellene blir ytelsestestet og sammenlignet med hverandre. Våre resultater viser at begge de temporale modellene er gunstige for temporal grafprosessering i Apache Spark, men at SnapshotDelta-modellen er jevnt over raskere. Modellen tar til gjengjeld mer plass. Til tross for at Tempura viser seg til å være effektiv, utvidbar og fleksibel, identifiserer vi flere nøkkelpunkt som både kan utforskes og videreutvikles, som å implementere nye temporale modeller og nye temporale spørringer.

Data is generated more frequently than ever. Increased data velocity, volume, and variety require expressive data models and tools for efficient processing and storage. Data is not only created but also updated. Thus solutions for monitoring how it changes become important to understand business needs. Many big data practitioners do not record how their data is updated, leading to missed opportunities in analyzing historical trends. There is no set standard of how to model temporal data, i.e., data that changes. Although relational databases is the industry standard for storing and querying data, the data can often easily be modeled as a graph. To lessen the task of temporal graph modeling, we introduce Tempura as a system for transforming and processing temporal graph data in a distributed setting. As few available datasets suit Tempora's features, we introduce a framework for augmenting existing temporal graph data. We extend Apache Spark and implement two promising models from related work on temporal graph data structures. The ValidityModel associates time intervals to entities to indicate when it is valid, and the SnapshotDeltaModel creates snapshots at certain intervals while keeping the in-between changes stored in deltas. Both are implemented behind a common interface so the API is model agnostic. The models are tested and benchmarked against each another. Our findings show that both models are viable for temporal graph processing in Apache Spark but that the SnapshotDeltaModel is faster. In return, the model demands more storage. Although Tempura offers to be an efficient, expandable, and flexible extension, we identify several key features that can be further explored or developed, such as implementing other temporal models and new temporal operations.