Skálázható gráflekérdezési technikák teljesítménymérése

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

A '70-es évektől kezdve az adatbáziskezelés jellemzően a relációs-alapú techológiák alkalmazását jelentette. Az elmúlt évtizedben viszont több olyan adatbázis jelent meg, amely nem relációs adatmodellre épül, mint például a gráfadatbázisok. Ezen adatbázisok, amelyek natívan támogatják a gráfok kezelését, illetve a felhasználók általi gráflekérdezéseket, mint például mintaillesztések, bejárások, vagy a legrövidebb utak keresése. Emellett megjelentek olyan új gráffeldolgozó rendszerek, amelyek támogatják a felhasználók által megírt algoritmusok futtatását (például mélységi keresés vagy PageRank) magas szintű programozási interfészeken keresztül, és végrehajtását elosztott rendszereken. Míg mindkét kategória rendszerei egyre komolyabb népszerűségnek örvendenek, sok rendszer komoly teljesítményproblémákkal küzd és nem képes nagy gráfokra skálázódni. Ezen túl hiányzik egy olyan egységes elmélet a gráffeldolgozási terhelési profilokra, mely lefedi mind a gráfadatbázisok lekérdezéseit, mind a gráfanalitikai algoritmusokat.

A GraphBLAS egy új kezdeményezés, melynek célja, hogy egy olyan szabványos programozási felületet definiáljon, amellyel a gráfalgoritmusokat a lineáris algebra nyelvén írhatjuk le. A GraphBLAS újszerűsége miatt szükséges a használhatóságának és a teljesítményének részletes vizsgálata. Ehhez a Linked Data Benchmark Council (LDBC) teljesítménymérési keretrendszereit használtam. A dolgozatban először bemutatom a GraphBLAS alapjait és az LDBC keretrendszereket. Ezután részletezem az LDBC Graphalytics három algoritmusának (szélességi keresés, egy pontból indított legrövidebb utak és lokális klaszterezettségi együttható) implementálása során szerzett tapasztalatokat és elemzem ezek szintetikus gráfokon mutatott teljesítményét. Végül tárgyalom az eredmények alkalmazhatóságát az LDBC Közösségi Hálózat Benchmarkban (Social Network Benchmark) található Üzleti Intelligencia (Business Intelligence) terhelési profil gráflekérdezéseinek kiértékelésére. Ezen keresztül bizonyítom, hogy a bemutatott GraphBLAS-alapú építőkockák felhasználhatók lehetnek mind hatékony gráfanalitikai rendszerek, mind skálázható gráflekérdező motorok megvalósításához.

Letölthető fájlok

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