Skip to contents

Comparison of nuggets performance with arules nad fim4r

Source: vignettes/comparison-with-arules.Rmd
comparison-with-arules.Rmd

Introduction

This vignette compares the performance of the following R packages:

  • nuggets 2.2.2
  • arules 1.7.14
  • fim4r 1.8 (installed and executed via arules)

The task of interest is the discovery of association rules in Boolean (TRUE/FALSE) datasets. The goal is to provide a comparison of brute computational power rather than a full comparison of package functionality, so advanced features, filtering options, and other factors that may affect practical performance are not considered here.

The following algorithm implementations were evaluated and compared with nuggets:

  • apriori (arules)
  • apriori (fim4r)
  • eclat (arules)
  • eclat (fim4r)
  • fpgrowth (fim4r)
  • relim (fim4r)
  • sam (fim4r)

For reproducibility, the benchmark script used in this vignette is available in the package repository on GitHub.

Materials and Methods

A series of experiments were conducted to evaluate the performance of the nuggets, fim4r, and arules packages. For arules, two different algorithms were evaluated: the Apriori algorithm (apriori()) and and the Eclat algorithm (eclat()). For fim4r, five different algorithms were evaluated: Apriori, Eclat, FP-Growth, Relim, and SAM (fim4r algorithms were executed via the arules package, see arules::fim4r()). For nuggets, the dig_associations() function was used to discover association rules.

The experiments were designed to measure the execution time of each method under different conditions, including varying the number of rows and columns in the datasets, as well as the sparsity of the data.

The test datasets were randomly generated with binary values (TRUE/FALSE) and varying numbers of rows and columns. The sparsity of the data was controlled by adjusting the probability of TRUE values in the dataset.

Specifically, the following parameters were varied in the experiments:

  • number of rows: 103, 104, 105, 106
  • number of columns: 10, 20, 30, 50, 80
  • the probability of TRUE values: 0.5 (dense datasets) and 0.1 (sparse datasets)

The other parameters were kept constant across all experiments:

  • the minimum support threshold: 0.001
  • the minimum confidence threshold: 0.5 (dense datasets) and 0.1 (sparse datasets)
  • the maximum length of antecedents: 3

Each experiment was repeated 5 times to ensure the reliability of the results, and the average execution time was recorded. All experiments were conducted on AMD Ryzen 9 5900X 12-Core Processor (512 KB cache) with 62.7 GB of RAM available under the GNU/Linux operating system. The CPU frequency governor was set to “performance” mode and the running process was pinned to a single CPU core.

The results are visualized using both linear and logarithmic scales to provide insights into the performance characteristics of each method.

Results

Dense data: varying number of rows

Time [ms]
rows cols nuggets apriori (arules) apriori (fim4r) eclat (arules) eclat (fim4r) fpgrowth (fim4r) relim (fim4r) sam (fim4r)
1e+03 30 16 53 2588 47 2667 2641 1276 1281
1e+04 30 20 104 2430 58 2567 2407 1518 1510
1e+05 30 54 747 3038 197 3193 2880 2131 1941
1e+06 30 382 8867 10035 1696 12234 9882 9001 6317
1e+07 30 6165 109570 91620 17444 114317 60962 99087 47538

Dense data: varying number of columns

Time [ms]
rows cols nuggets apriori (arules) apriori (fim4r) eclat (arules) eclat (fim4r) fpgrowth (fim4r) relim (fim4r) sam (fim4r)
1e+05 10 9 71 62 34 62 61 47 46
1e+05 20 22 345 686 82 541 477 273 269
1e+05 30 55 775 3048 254 3202 2900 2165 1978
1e+05 50 327 2829 22467 1099 26146 24955 26466 24971
1e+05 80 2019 13955 150160 7015 171701 178611 187277 219270

Sparse data: varying number of rows

Time [ms]
rows cols nuggets apriori (arules) apriori (fim4r) eclat (arules) eclat (fim4r) fpgrowth (fim4r) relim (fim4r) sam (fim4r)
1e+03 30 8 15 638 14 628 629 182 177
1e+04 30 11 16 1278 17 1218 1253 87 84
1e+05 30 66 80 1346 85 1314 1320 148 146
1e+06 30 606 907 1794 743 1773 1714 503 550
1e+07 30 6262 15056 8521 8667 8135 7604 6116 6261

Sparse data: varying number of columns

Time [ms]
rows cols nuggets apriori (arules) apriori (fim4r) eclat (arules) eclat (fim4r) fpgrowth (fim4r) relim (fim4r) sam (fim4r)
1e+05 10 8 36 37 22 37 37 26 26
1e+05 20 26 57 281 45 259 271 85 83
1e+05 30 67 80 1347 85 1355 1347 116 112
1e+05 50 254 218 10480 315 11007 10831 416 415
1e+05 80 1057 390 71753 980 71500 71174 1546 1673

Discussion

As can be seen from the results, nuggets performance is consistently among the best. Only for sparse data with many columns, arules:apriori() becomes clearly more efficient.

nuggets is based on the ECLAT algorithm similarly as arules:eclat() or fim4r::fim4r_eclat(). Therefore, both variants are expected to perform similarly well. A likely explanation for the strong performance of nuggets on dense data is its highly optimized implementation of conjunction computation and support counting. These operations are central to rule discovery, and in nuggets they are accelerated using:

This makes the evaluation of candidate conjunctions fast particularly for dense datasets.

Note that all nuggets optimizations are available with the default compiler directives recommended by CRAN, without requiring any non-standard package installation settings.

Summary

The results show that nuggets is particularly effective for dense data, where its optimized implementation provides consistently strong performance. For sparse data with many predicates, however, arules, especially apriori(), becomes more advantageous.

For additional information on the nuggets package, see: