GPU akcelerace pro indukční logické dolování pravidel v grafech
| Název práce: | GPU Acceleration for Inductive Logic Rule Mining in Knowledge Graphs |
|---|---|
| Autor(ka) práce: | Naar, Vojtěch |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Zeman, Václav |
| Oponenti práce: | Sýkora, Lukáš |
| Jazyk práce: | English |
| Abstrakt: | This master thesis focuses on accelerating support and confidence computation in inductive logic rule mining over large RDF knowledge graphs. The work builds on AMIE-style Horn rule mining and the RDFRules framework, where candidate rules are evaluated by repeatedly executing join-like graph pattern matching operations over large triple sets. The thesis investigates whether this counting phase can be accelerated using native C++ implementations and NVIDIA CUDA GPU execution while preserving the original rule semantics. The practical contribution consists of a faithful C++ rewrite of the RDFRules counting logic, a cache-oriented CPU implementation based on CSR indexes, and a CUDA implementation that stores graph indexes in GPU memory and evaluates rules using massively parallel DFS kernels. The implementations are integrated with the Scala RDFRules framework through a shared native library and Java Native Access. Experimental evaluation on synthetic, DBpedia, and biomedical datasets shows that GPU acceleration is strongest when rule evaluation produces large body-size search spaces, while CPU-side CSR optimization is highly dependent on graph topology and may regress on high-fanout predicates. |
| Klíčová slova: | Logic rule; graph mining; GPU; CUDA; Parallelism |
| Název práce: | GPU akcelerace pro indukční logické dolování pravidel v grafech |
|---|---|
| Autor(ka) práce: | Naar, Vojtěch |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Zeman, Václav |
| Oponenti práce: | Sýkora, Lukáš |
| Jazyk práce: | English |
| Abstrakt: | Tato diplomová práce se zaměřuje na akceleraci výpočtu podpory a spolehlivosti při indukčním logickém dolování pravidel v rozsáhlých znalostních grafech ve formátu RDF. Práce vychází z dolování Hornových pravidel ve stylu AMIE a frameworku RDFRules, kde jsou kandidátní pravidla vyhodnocována opakovaným prováděním operací podobných spojení nad rozsáhlými množinami trojic. Práce zkoumá, zda lze tuto fázi počítání akcelerovat pomocí nativních implementací v jazyce C++ a GPU vykonávání prostřednictvím NVIDIA CUDA při zachování původní sémantiky pravidel. Praktický přínos práce spočívá ve věrném přepisu logiky počítání RDFRules do jazyka C++, v CPU implementaci orientované na paměťovou lokalitu využívající indexy ve formátu CSR a v implementaci CUDA, která ukládá grafové indexy do paměti GPU a vyhodnocuje pravidla pomocí masivně paralelních DFS jader. Implementace jsou integrovány s frameworkem Scala RDFRules prostřednictvím sdílené nativní knihovny a Java Native Access. Experimentální vyhodnocení na syntetické, DBpedia a biomedicínské datové sadě ukazuje, že GPU akcelerace je nejsilnější tehdy, když vyhodnocování pravidel generuje velké prohledávací prostory těl pravidel, zatímco CPU optimalizace pomocí CSR je silně závislá na topologii grafu a může vykazovat regresi u predikátů s vysokým větvením. |
| Klíčová slova: | CUDA; dolování z grafů; grafová pravidla; Paralelismus; GPU |
Informace o studiu
| Studijní program / obor: | Znalostní a webové technologie |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra informačního a znalostního inženýrství |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 4. 12. 2025 |
|---|---|
| Datum podání práce: | 4. 5. 2026 |
| Datum obhajoby: | 8. 6. 2026 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/94803/podrobnosti |