The past years have shown an increasing demand to process data of various kinds and size in real-time. A common representation for many real-world scenarios is a graph, which shows relations between entities, such as users of social networks or pages on the Internet. These graphs increase in size over time and can easily exceed the capacity of single machines.Graph partitioning is used to divide graphs into multiple subgraphs on different servers. Traditional partitioning techniques work in an offline manner where the whole graph is processed before partitioning. Due to the recently increased demand for real-time analysis, online partitioning algorithms have been introduced. They are able to partition a graph arriving as a stream, also referred to as a streaming graph, without any pre-processing step.The goal of a good graph partitioning algorithm is to maintain the data locality and to balance partitions’ load at the same time. Although different algorithms have proven to achieve both goals for real-world graphs, they often require to maintain a state. However, modern stream processing systems, such as Apache Flink, work with a shared-nothing architecture in a data-parallel manner. Therefore, they do not allow to exchange information along with parallel computations. These systems usually use Hash-based partitioning, that is a fast stateless technique but ignores the graph structure. Hence, it can lead to longer analysis times for streaming applications which could benefit from preserved structures.This work aims to develop a state-sharing parallel streaming graph partitioner for Apache Flink, called WinBro, implementing well-performing partitioning algorithms. In order to do this, existing streaming graph algorithms are studied for possible implementation and then integrated into WinBro.For validation, different experiments were made with real-world graphs. In these experiments, the partitioning quality, and partitioning speed were measured. Moreover, the performance of different streaming applications using WinBro was measured and compared with the default Hash-based partitioning method.Results show that the new partitioner WinBro provides better partitioning quality in terms of data locality and also higher performance for applications with requirements for locality-based input data. Nonetheless, the Hash-based partitioner shows the highest throughput and better performance for data localityagnostic streaming applications. / De senaste åren har det skett en ökande efterfrågan på att bearbeta data av olika sorter och storlek i realtid. En vanlig representation för många scenarier är diagram som visar relationer mellan enheter, till exempel användare av sociala nätverk eller sidor på Internet. Dessa grafers storlek ökar över tiden och kan enkelt överstiga kapaciteten hos individuella maskiner.Grafpartitionering används för att dividera grafer i flera delgrafer på olika servrar. Traditionella partitioneringstekniker fungerar offline, där hela grafen bearbetas före partitionering. Baserat på den nyligen ökade efterfrågan på realtidsanalys har online-partitionsalgoritmer introducerats. De kan partitionera en graf som kommer strömmande, även kallad ett strömmande diagram, utan förbehandling.Målet med en bra grafpartitioneringsalgoritm är att behålla datalokalitet och balansera partitionernas belastning samtidigt. Även om olika algoritmer har visat möjligheten att uppnå båda målen för realvärldsgrafik, behöver de ofta behålla ett tillstånd. Moderna strömbehandlingssystem, som Apache Flink, arbetar emellertid med en gemensam-ingenting-arkitektur på ett data-parallellt sätt. Därför tillåter de inte att utbyta information under parallella beräkningar. Dessa system brukar använda Hash-baserad partitionering, vilket är en snabb tillståndslös teknik men ignorerar grafstrukturen. Därför kan det leda till längre analystider för strömmande applikationer som kan dra nytta av bevarade strukturer.Detta arbete har som mål till att utveckla en tillstånsdsdelande, parallellströmmande grafpartitionering för Apache Flink, kallad WinBro, som implementerar välpresterande partitioneringsalgoritmer. För att nå målet studeras befintliga strömmande grafalgoritmer för möjlig implementering och sedan integreras i WinBro.För validering görs olika experiment med realvärldsgrafik. I våra experiment mäter vi partitioneringskvaliteten och partitioneringshastigheten. Dessutom kvantifierar vi prestanda för olika strömmande applikationer med WinBro och jämför den med en standard Hash-baserad partitionsmetod.Resultat visar att den nya partitionern WinBro ger bättre partitioneringskvalitet när det gäller datalokalitet och även högre prestanda för applikationer med krav på lokalitetsbaserad inmatningsdata. Alternativt visar den Hashbaserade partitionen den högsta genomströmningen och bättre prestanda för datalokalitets-agnostiska strömmande applikationer.

Counting object in pictures is a computer vision task that has been explored in the past years, achieving state-of-the-art results thanks to the rise of convolutional neural networks. Most of the work focused on specific and limited domains to predict the number of just one category in the likes of people, cars, cells, and animals. Little effort has been employed to investigate methods to count the instances of different classes at the same time. This thesis work explored the different approaches present in the literature to understand their strenghts and weaknesses and eventually improve the accuracy and reduce the inference time of models aimed to estimate the number of multiple elements. At first, new techniques have been applied on top of the previously proposed algorithms to lower the prediction error. Secondly, the possibility to adapt an object detector to the counting task avoiding the localization prediction has been investigated. As a result, a new model called Single-Shot Multiscale Counter has been proposed, based on the architecture of the Single-Shot Multibox Detector. It achieved a lower prediction error on the ground truth count by 11% (from an mRMSE of 0.42 to 0.35) and an inference time 16x to 20x faster compared to the models found in the literature (from 1.25s to 0.049s). / Att räkna objekt i bilder är en datorvisionsuppgift som har utforskats under de senaste åren och uppnått toppmoderna resultat tack vare ökningen av invändiga neurala nätverk. De flesta av arbetena fokuserade på specifika och begränsade domäner för att förutsäga antalet bara en kategori som människor, bilar, celler och djur. Liten ansträngning har använts för att undersöka metoder för att räkna förekomsten av olika klasser samtidigt. Detta avhandlingsarbete utforskade de olika metoder som finns i litteraturen för att förstå deras styrka och svagheter och så småningom förbättra noggrannheten och minska inferingstiden för modeller som syftar till att uppskatta antalet flera element. Först har nya tekniker tillämpats ovanpå de tidigare föreslagna algoritmerna för att sänka förutsägelsefelet. För det andra har möjligheten att anpassa en objektdetektor till räkneuppgiften för att undvika lokaliseringsförutsägelse undersökts. Som ett resultat har en ny modell som heter Single-Shot Multiscale Counter föreslagits, baserad på arkitekturen för Single-Shot Multibox Detector. Den uppnådde ett lägre förutsägelsefel på sanningsräkningen på marken med 11 % (från en mRMSE på 0,42 till 0,35) och en slutningstid 16x till 20x snabbare jämfört med modellerna som finns i litteraturen (från 1,25 till 0,049 sek).

In this work, we present a novel approach to the streaming graph partitioning problem which handles unbounded streams.Graph partitioning is a process of dividing a graph into groups of nodes or edges. Traditional, offline partitioning methods require a priori access to the entire graph and make multiple passes over the data in order to compute partitions. However, recently the demand for real-time analysis of graph data sparked the prospect of online partitioning. In such an approach, the graph arrives as a stream of nodes or edges which are assigned to partitions as they come and are never reassigned again. Additionally, in the case of modern systems, where graphs constantly grow, the streams are unbounded. The main goals of graph partitioning are preserving data locality, so related items belong to the same partitions, and load balance, so partitions have similar sizes.State-of-the-art streaming graph partitioning algorithms fulfil the two latter requirements. However, they make their partitioning decisions based on internal state, which grows as new items arrive. Thus, they are not capable of processing unbounded streams. At some point, the state will exceed the memory capacity of the machine the algorithm is running on. Moreover, modern stream data processors run in a distributed environment. In such a setting synchronisation of a shared state is an expensive operation.In the proposed approach, in addition to structural information about the graph, we utilise attributes associated with vertices such as user’s location, age, or previous actions. In order to do that, we employ a graph convolutional network (GCN), which is a novel method of graph representation learning. A GCN can embed both structural and feature-based characteristics of each vertex into a low-dimensional space. Secondly, we feed these representations into a neural network, which assigns incoming items to partitions. Such a method requires only the networks’ parameters’ values in order to make a partitioning decision. Thus, the size of the state remains constant regardless of the length of the stream.We present both unsupervised and supervised approaches to train the proposed framework. Moreover, we describe a method to apply the models to partition the streaming graph. We evaluate the performance of our novel method on three real-world graph datasets and compare it with the state-of-the-art HDRF algorithm as well as a simple, stateless hash-based approach. The experimental results show the generalisation capabilities of our models. Moreover, our methods can yield up to 16% lower replication factor than hash partitioning which corresponds to only 1% increase compared to HDRF. At thesame time, we reduce state requirements from linear to constant, which for the graph with 230k vertices and 5.7M edges translates to 125 times smaller size of the state and allows for processing unbounded streams. Nevertheless, the latency of our methods is about 20 times higher than HDRF. / I det här arbetet presenterar vi en ny metod för grafpartitionering av obundna strömmar.Grafpartitionering är en process att dela upp en graf i grupper av noder eller kanter. Traditionella, offline-partitioneringsmetoder kräver en priori åtkomst till hela grafen och gör flera passeringar över datan för att beräkna partitioner. Nyligen gjorde dock efterfrågan på realtidsanalys av grafdata möjligheterna att partitionera online. I ett sådant tillvägagångssätt ankommer grafen som en ström av noder eller kanter som tilldelas partitioner när de kommer och aldrig tilldelas igen. Dessutom, för moderna system, där grafer ständigt växer, är strömmarna obegränsade. Huvudmålen för grafpartitionering är att bevara datalokalitet, så relaterade objekt tillhör samma partitioner och lastbalans, så partitioner har liknande storlekar.Avancerade algoritmer för strömmande grafpartitionering uppfyller de två senare kraven. De fattar emellertid sina partitionsbeslut baserade på internt tillstånd, som växer när nya artiklar kommer. Således kan de inte bearbeta obundna strömmar. Vid någon tidpunkt kommer tillståndet att överskrida minneskapaciteten för maskinen som algoritmen kör på. Dessutom körs moderna databehandlare i en distribuerad miljö. I en sådan inställning är synkronisering av ett delat tillstånd en dyr operation.I det föreslagna tillvägagångssättet använder vi, utöver strukturell information om grafen, attribut som är förknippade med hörn som användarens plats, ålder eller tidigare åtgärder. För att göra det använder vi ett grafkonvolutional nätverk (GCN), som är en ny metod för grafrepresentation. En GCN kan bädda in både strukturella och funktionsbaserade egenskaper hos varje toppunkt i ett lågdimensionellt utrymme. För det andra matar vi dessa representationer i ett neuralt nätverk, som tilldelar inkommande objekt till partitioner. En sådan metod kräver bara nätverksparametrarnas värden för att fatta ett partitionsbeslut. Således förblir tillståndets storlek konstant oavsett strömmens längd.Vi presenterar både obevakade och övervakade tillvägagångssätt för att utbilda det föreslagna ramverket. Dessutom beskriver vi en metod för att tillämpa modellerna för att partitionera strömningsgrafen. Vi utvärderar prestandan för vår nya metod på tre grafiska datauppsättningar i verkligheten och jämför den med den senaste HDRF-algoritmen samt en enkel, statslös hashbaserad strategi. De experimentella resultaten visar generaliseringsförmågan hos våra modeller. Dessutom kan våra metoder ge upp till 16% lägre replikationsfaktor än hashpartitionering, vilket motsvarar endast 1% ökning jämfört med HDRF. Samtidigt minskar vi tillståndskraven från linjär till konstant,vilket för diagrammet med 230k vertikaler och 5,7M kanter motsvarar 125 gånger mindre storlek på tillståndet. Trots det är latens för våra metoder ungefär 20 gånger högre än HDRF.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.