Gráfelemzési algoritmus fejlesztése Apache Spark alapokon

OData támogatás
Konzulens:
Prekopcsák Zoltán
Távközlési és Médiainformatikai Tanszék

Jelen diplomaterv egy gráfalgoritmus, a maximális méretű klikk keresésének elosztott megvalósításával foglalkozik. A feladat fontos célkitűzése egy jól skálázódó, párhuzamosított algoritmus kidolgozása, emiatt az Apache Spark keretrendszer segítségével került megvalósításra. A Spark központi funkcionalitásában számos olyan elemet nyújt, amely segít a feladat elosztott megvalósításában, gráffeldolgozásért felelős GraphX komponense pedig gráfokra specializált funkciókkal könnyíti meg a munkát.

A probléma megoldására számos publikált algoritmus létezik, melyek vizsgálatára a dolgozat nagy hangsúlyt fektet. Ez egzakt és közelítő algoritmusok mellett különböző segédeljárások vizsgálatát egyaránt magában foglalja.

A bemutatott algoritmusok szinte kivétel nélkül szekvenciálisak, ezért Spark keretrendszerhez illő párhuzamosításuk a dolgozat legfontosabb feladata. Ennek kivitelezésére több alternatíva is bemutatásra kerül. A fő megoldások a keresési tér bejárásának módjában és az adatok végrehajtó node-ok közötti mozgatásának szervezésében térnek el. Emellett a dolgozat apróbb optimalizációkkal is foglalkozik, amelyek tovább javítják az alapmegoldások teljesítményét. Ezen optimalizációk egy része logikai alapokra épül, a technikai megvalósítástól független, míg másik részük a Sparkhoz köthető technikai jellegű finomítás.

Az elkészült szoftverek validálása teljesítménytesztelés segítségével történt, amely egy klaszteren lett végrehajtva. A mérések különböző méretű és jellegű bemeneti gráfok segítségével lettek elvégezve, ami a megoldások alapos összehasonlítását biztosítja.

A dolgozatban látható, hogy a Spark architektúrája nem minden esetben illeszkedik teljesen a kitűzött feladathoz. Azonban ezzel együtt is alkalmas egy jól skálázódó, számos bemeneten jól teljesítő szoftver kidolgozására.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.