Systems for Efficient Storage and Retrieval of Dynamic Networks

Abstract

En enorm mengde data skapes hver dag. Nye fremskritt innen maskinvare og programvare gjør det mulig for bedrifter å lagre mer omfattende og mer detaljerte datamengder. Dataene inneholder større variasjon, kommer i økende volum og med enda større hastighet. Bedrifter og bransjer har forstått at deres underliggende datamodell kan representeres som et nettverk, og at utnyttelse av dette kan forbedre måten de lagrer og analyserer viktig informasjon på.

Denne masteroppgaven ser på det faktum at store deler av disse nettverksdataene kan lagres av en underliggende eiendomsgraf. Noder og kanter danner byggesteinene til alle grafer, og når de kombineres kan de skape komplekse strukturer. I løpet av de siste århundrene har forskere utviklet metoder og algoritmer for å resonnere rundt slike grafer og har oppdaget utrolige måter å få nettverksinnsikt på. Et problem med disse metodene oppstår når tar i betraktning at de fleste nettverk ikke er statiske, men heller dynamiske og levende.

Å lagre en aktivt utviklende graf krever nye løsninger i form av et et system som kan akkumulere nye endringer. Videre krever identifisering av mønstre for å få innsikt i skiftende grafer nye metoder. De temporalen aspektene gir nye problemer, men åpner også opp for nye løsninger. I denne masteroppgaven er et prototypesystem bygget for å lagre dynamiske grafer. Det foreslåtte systemet er forankret i virkeligheten og tar sikte på å åpne verden opp til temporalsk lagring og analyse ved å tilgjengeliggjøre et GraphQL API som kan mutere og spørre etter temporalsk data. Vi viser at det er mulig å bygge en slik modell i Dgraph. Til slutt gjennomgår vi et sett med resultater som viser lovende ytelse innen hastighet og evner.

An enormous quantity of data is created every day. New advances in hardware and software allow companies to store more extensive and more detailed amounts of data. The data contain greater variety, is arriving in increasing volumes and with even more velocity. Businesses and industries have caught on to the fact that their underlying data model can be represented as a network and that taking advantage of this can propel the way they store and analyse essential information.

This Master's Thesis looks at the fact that large portions of this network data can be stored by an underlying property graph. Nodes and edges form the building stones of all graphs and, when combined, can create the most complex structures imaginably. During the last centuries, scientists and researchers have developed methods and algorithms to reason about such graphs and discovered incredible ways to get network insight. A problem with these methods arises when considering that most networks are not static but rather quite dynamic and evolving.

Storing an actively evolving graph calls for new solutions as a system must accumulate recent changes. Furthermore, identifying patterns and gaining insight into ever-changing graphs requires new methods. The temporal aspect adds new problems but also opens up new solutions. In this Master's Thesis, a prototype system is built to facilitate time-varying graphs. The proposed approach is grounded in reality and aims to open the world of temporal storage and analytics to the masses by enabling a GraphQL API that can mutate and query temporal data. We show that it is possible to build such a model in Dgraph using a frame model. This model allows tracking changes by associating nodes with their active timestamps. Furthermore, the model enables specific indexes to be built, allowing a vast array of temporal queries to be submitted. Lastly, we review a set of results previewing promising performance within speed and capabilities.