Frameworks for Distributed Processing of Temporal Graph Queries
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3088034Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Sammendrag
Grafdatamodellen er en av de fundamentale datastrukturene vi har og spiller en sentral rolle i domener som sosiale nettverk, trafikknettverk og sensornettverk. Nå som data genereres og samles kontinuerlig, blir tidspunktene av forskjellig hendelser i disse domenene viktigere for å forstå og analysere dem. Siden datavolumet bare vokser er horisontal skalering som tillater distribuert prosessering med flere maskiner en nødvendighet. Med utgangspunkt i dette har det vært en økende interesse i forskningslitteraturen for rammeverk som utvider denne grafdatamodellen. I vår litteraturstudie organiserer vi disse utvidelsene i temporale grafmodeller, temporale grafspørringer, og distribuerte programmeringsmodeller. Dessuten har vi oppdaget at det er en mangel av spørringsfunksjonalitet som tillater de nye temporal grafspørringene med vektede spørringer. Derfor har vi laget en prototype hvor vi har innarbeidet denne funksjonaliteten som en utvidelse. Vår løsning viser varierende resultater, men for de fleste spørringer er den i stand til å skalere med større datasett, dyrere parametere og tendenser til økning i ytelse med flere arbeidsnoder. Dermed viser arbeidet vårt at det er mulig å prosessere temporale grafspørringer distribuert, og åpner for videre forskningsmuligheter for disse spørringene, som inkluderer database- eller strøm orienterte systemer. The graph data model is one of the fundamental data structures we have and is playing a crucial role in domains such as social networks, traffic networks and sensor networks. As data is continuously collected and generated, the time of different events in these domains are becoming increasingly more important for analysing and understanding them. In addition, as the data volume only grows, horizontal scaling facilitating distributed processing with multiple machines is a necessity. With this context in mind, there have been an increasing interest in the research literature for frameworks that extend this graph data model. In our literature review, we find that these framework extensions can be organized in temporal graph models, temporal graph queries and distributed programming models. Furthermore, we find that there is a lacking of query functionality that allow for the new type of temporal path queries with the addition of weighted path queries. We therefore made a prototype where we incorporated this functionality as an extension. Our solution shows varying results, but for most queries it is able to scale with larger datasets, more expensive parameters and tendencies of speedups with increasing worker nodes. Thus, this work shows the feasibility of processing temporal graph queries in distributed settings, and opens up for further research directions for these queries, which include database or stream oriented systems.