Memory-Efficient Bit-Level GPU Optimizations for Action Rule Mining

Thesis title: Memory-Efficient Bit-Level GPU Optimizations for Action Rule Mining
Author: Karpe, Vladislav
Thesis type: Bachelor thesis
Supervisor: Sýkora, Lukáš
Opponents: Máša, Petr
Thesis language: English
Abstract:
Action rule mining identifies attribute changes that move records from an undesired to a desired class. This thesis rebuilds the Action-Apriori algorithm around a packed-bitset rep- resentation: support for many candidates is counted in a single bitwise pass, executed on the CPU or by a custom CUDA kernel on the GPU. An autotuner selects the backend from dataset characteristics, and an asynchronous warmup overlaps CUDA initialization with data preprocessing. On three real classification datasets, the autotuned miner is an order of magnitude faster than the reference action-rules package on the smaller two. On the largest, it finishes in 1.5 seconds while the reference does not complete within fifteen minutes; peak RAM on the adult dataset drops from 2.3 GB to 42 MB. The same bitset core is also exposed as a standalone frequent-itemset miner, beating pyfim Eclat — the fastest Python implementation tested — on the largest dataset. Every configuration produces identical rule sets, so the runtime gains do not change what the miner finds.
Keywords: GPU acceleration; CUDA; parallelization; packed bitsets; action rule mining; frequent itemset mining; open-source; Action-Apriori
Thesis title: Paměťově Efektivní Bitové Optimalizace Pro Action Rule Mining Na GPU
Author: Karpe, Vladislav
Thesis type: Bakalářská práce
Supervisor: Sýkora, Lukáš
Opponents: Máša, Petr
Thesis language: English
Abstract:
Dolování akčních pravidel (action rule mining) identifikuje změny atributů, které vedou k přesunu záznamů z nežádoucí do žádoucí třídy. Tato práce přepracovává algoritmus Action-Apriori pomocí reprezentace založené na kompaktních bitových vektorech (packed bitsets), díky níž lze podporu velkého množství kandidátů počítat v jediném průchodu pomocí bitových operací prováděných buď na CPU, nebo prostřednictvím vlastní CUDA implementace na GPU. Autotuner vybírá vhodný backend na základě charakteristik datasetu a asynchronní warm-up fáze překrývá inicializaci CUDA s předzpracováním dat. Na třech reálných klasifikačních datasetech dosahuje autotuned implementace oproti referenčnímu balíčku action-rules řádově vyšší rychlosti u dvou menších datasetů. U největšího datasetu dokončí výpočet za 1,5 sekundy, zatímco referenční implementace nedokončí běh ani po patnácti minutách. Na datasetu Adult zároveň klesá maximální využití operační paměti z 2,3 GB na 42 MB. Stejné bitové jádro je rovněž dostupné jako samostatný algoritmus pro dolování frekventovaných itemsetů, kde na největším datasetu překonává pyfim Eclat, nejrychlejší testovanou implementaci v Pythonu. Ve všech konfiguracích jsou generovány identické množiny pravidel, takže dosažené výkonové zlepšení nemění výsledky samotného dolování.
Keywords: action rule mining; GPU akcelerace; Action-Apriori; packed bitsets; CUDA; dolování frekventovaných itemsetů; paralelizace; open-source software

Information about study

Study programme: Aplikovaná informatika
Type of study programme: Bakalářský studijní program
Assigned degree: Bc.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Information and Knowledge Engineering

Information on submission and defense

Date of assignment: 29. 10. 2025
Date of submission: 11. 5. 2026
Date of defense: 15. 6. 2026
Identifier in the InSIS system: https://insis.vse.cz/zp/94284/podrobnosti

Files for download

    Last update: