Nagyméretű, gráfstruktúrájú adathalmaz elemzése

OData támogatás
Konzulens:
Dr. Bergmann Gábor
Méréstechnika és Információs Rendszerek Tanszék

Manapság a legtöbb ember számára az interneten való keresés és adatok feltöltése teljesen megszokott. Azonban a több milliárd felhasználó által létrehozott adathalmaz olyan óriási mennyiségű is lehet, amit egy számítógépen már nem lehet feldolgozni, ezt nevezzük Big Datanak.

Többféle számítási modell segítségével tudjuk feldolgozni ezeket a hatalmas adathalmazokat, az egyik legelterjedtebb a Google által fejlesztett Pregel modell. A Big Data technológiák egyike az Apache Flink, amely elosztott számítást tesz lehetővé. A Pregel modellen alapuló Flink Gelly gráfkönyvtár pedig a nagyméretű gráfok feldolgozását segíti.

Ha elosztott algoritmust szeretnénk implementálni Big Data elemzéséhez, akkor figyelnünk kell a hatékony és helyes megvalósításra, mivel a programokat (a nagy adatmennyiség és az elosztottság miatt) nem tudjuk könnyen ellenőrizni, javítani.

A szakdolgozatomban a BME CrySyS Lab által létrehozott, gráf jellegű ROSCO kriptográfiai adathalmazát vizsgálom, ez tanúsítványt használó és azokat aláíró szervezetekből áll. Ha irányított köröket keresünk ebben a gráfban, akkor egymást körkörösen aláíró csomópontokat találhatunk, amely biztonsági problémákat jelezhet.

A fenti célból megvalósítom az erősen összefüggő komponensek detektálását (a) lokálisan a Tarjan algoritmus alapján és (b) elosztottan egy Pregel modellen alapuló algoritmus szerint. Továbbá ellenőrzöm az algoritmusok helyességét unit tesztek segítségével.

A lokális és elosztott algoritmusokat kipróbálom a ROSCO gráf részhalmazain és egészén, végül a futtatás során kapott eredmények kezdeti vizsgálatát is elvégzem.

Letölthető fájlok

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