Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

A Data Structure Perspective to the RDD-based Apriori Algorithm on Spark

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For Spark Apriori, replacing Hash Tree with Trie or Hash Table Trie speeds up runs by up to eight times on benchmark data.

desk verdict A plausible but under-verified Spark-specific comparison of candidate-storage data structures for Apriori; the direction is believable, but missing parameters and code make the magnitude uncheckable. read the letter →

arxiv 1908.01338 v1 pith:F6DHSHVU submitted 2019-08-04 cs.DC cs.DB

Pankaj Singh , Sudhakar Singh , P. K. Mishra , Rakhi Garg This is my paper · ORCID
classification cs.DCcs.DB
keywords frequentitemsetminingAprioriApacheSparkRDDHashTreeTrieTabledatastructures
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Apriori finds sets of items that co-occur frequently in transactional data, and its cost is dominated by generating candidate sets and counting their support. The paper asks whether the data structure used to store those candidates changes the runtime of a Spark (RDD-based) version of Apriori. It reports that on all seven benchmark datasets, replacing the usual Hash Tree with a Trie or a Hash Table Trie cuts execution time substantially: at least eight times on BMS_WebView_1 and BMS_WebView_2 and about six times on T40I10D100K at the lowest support tested. The two Trie-based variants perform about the same as each other. If the reported ranking is right, existing Spark Apriori implementations built on Hash Trees are leaving a large, structure-level speedup unused.

What carries the argument

The central object is the candidate-set container used by the two computationally intensive routines of Apriori: apriori-gen(), which builds candidate itemsets from frequent itemsets of the previous level, and subset(), which checks each transaction against the candidates. A Hash Tree stores candidate itemsets in leaf buckets reached by hashing and depends on two heuristic tuning parameters, child_max_size and leaf_max_size. A Trie stores itemsets as shared prefixes along root-to-leaf paths, with no such parameters; a Hash Table Trie is the same structure with a hash table at each node to make downward traversal faster. In the paper's experiments, swapping the candidate-store inside otherwise identical RDD-Apriori variants is the entire intervention, so the data structure is the variable that explains the observed differences in execution time.

What would settle it

Rerun the three variants on the same seven datasets with the same cluster, openly reporting and systematically varying the Hash Tree's child_max_size and leaf_max_size values, and repeat each configuration several times to get variance; if some Hash Tree setting brings its runtime down to the Trie level on BMS_WebView_1 or BMS_WebView_2, the reported ranking is an artifact of parameter choice rather than a property of the data structures.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes a measured performance ranking rather than a new algorithm. It implements three variants of an RDD-based Apriori that differ only in the data structure used for the candidate sets and frequent itemsets of the previous level: Hash Tree, Trie, and Hash Table Trie. Across seven synthetic and real-life datasets, the Trie and Hash Table Trie variants are consistently and often dramatically faster than the Hash Tree variant, with the largest gaps on the two BMS datasets and on T40I10D100K. The execution times of the two Trie variants are close enough that the paper calls the difference not significant. It concludes that Trie-family structures, not Hash Trees, are the suitable candidate-store for Spark-based Apriori, and that the Hash Table Trie advantage seen in earlier MapReduce experiments does not carry over to Spark's in-memory RDD environment.

Load-bearing premise

The ranking stands on the assumption that the three implementations differ only in the data structure: the Hash Tree's heuristic parameters were set fairly, the Trie-family code is comparable in quality, and the single timed runs are representative.

Editorial extensions

If this is right

  • Spark-based Apriori implementations should prefer a Trie or Hash Table Trie over a Hash Tree for candidate storage, since the same algorithm runs many times faster on all tested datasets.
  • The extra hashing in Hash Table Trie buys little on Spark; a plain Trie is enough to capture the speedup.
  • The data-structure ranking from MapReduce-era experiments does not transfer automatically: Hash Table Trie's MapReduce advantage over Trie largely disappears on Spark.
  • On the paper's measurements, existing Spark Apriori systems built on Hash Trees can gain a large constant-factor speedup by a structure swap alone, without changing the parallelization strategy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper uses one fixed local cluster and does not report the Hash Tree tuning parameters; a natural next check is whether the Trie advantage persists across cluster sizes, partition counts, and a systematic sweep of those parameters.
  • Because the largest speedups occur on datasets with many short transactions, the result hints that the Trie's advantage grows with candidate-set size relative to transaction width; this connection is not tested in the paper.
  • A direct engineering extension would be to profile cache misses and node sizes for the three structures on Spark, which would test the paper's explanation of why Hash Table Trie stays competitive on Spark.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper presents an empirical study of three underlying data structures for an RDD-based Apriori algorithm on Apache Spark: Hash Tree, Trie, and Hash Table Trie. It implements three variants of a YAFIM-style RDD-Apriori that differ only in the data structure used for candidate generation and subset checking, and measures execution time on seven benchmark datasets (c20d10k, chess, mushroom, BMS_WebView_1, BMS_WebView_2, T10I4D100K, T40I10D100K) over varying minimum support. The central result is that the Trie and Hash Table Trie variants outperform the Hash Tree variant on every dataset, with speedups of about six to eight times at the lowest support on several datasets, while the two Trie-family variants perform similarly. The paper also interprets the results in comparison with a previous MapReduce-based study on the same data structures.

Significance. If the reported ranking is taken at face value, the paper gives useful practical guidance: Spark-based Apriori implementations should prefer Trie or Hash Table Trie over Hash Tree for candidate storage. The direction of the result is consistent with prior sequential results and with the authors' earlier MapReduce results, and the breadth of seven datasets is a strength. However, the empirical claim is currently undercut by the lack of reported heuristic parameters for the Hash Tree baseline, the absence of repeated runs or variance measures, and the absence of released code; these are needed to establish that the measured speedups are due to the data structure itself rather than to tuning or implementation artifacts.

major comments (3)
  1. [Section 4.2 and Section 5.2] The paper states that the Hash Tree uses two heuristic parameters, child_max_size and leaf_max_size, but never reports the values used for any of the seven datasets. Because RDD-HashTree-Apriori is the baseline and the Trie and Hash Table Trie variants are in-house implementations, the central speedup claim cannot be separated from possible mis-tuning of the baseline; please provide the parameter values per dataset and a sensitivity analysis over a reasonable range.
  2. [Section 5.2 and Figs. 4(a-g)] All execution times appear to be from a single run; no error bars, standard deviations, or significance tests are reported. The claim that the Trie variants significantly outperform Hash Tree, and that the difference between Trie and Hash Table Trie is not significant, therefore lacks statistical support; please report repeated runs with variance and a statistical test.
  3. [Section 5.1] The manuscript states only that all source code is written in Java-7 and provides no repository or artifact. With the Hash Tree parameters unreported, the experiments cannot be reproduced or checked; please release the code and configuration, including Spark settings and dataset preprocessing, as supplementary material, or at minimum give exact implementation details and parameter values.
minor comments (3)
  1. [Section 4.1 and Section 5.1] There are several typos and grammar errors: 'Phaes-2' should be 'Phase-2', 'Intel Xenon' should be 'Intel Xeon', and 'self-explainatory' should be 'self-explanatory'.
  2. [Section 5.2] The discussion comparing Spark results with the MapReduce results from reference [19] does not acknowledge that the cluster, dataset versions, and implementation environment differ; this cross-platform comparison should be framed as a qualitative trend rather than a direct quantitative comparison.
  3. [Figs. 4(a-g)] The figure captions do not define the line styles or markers used for the three algorithms; please add a legend or state explicitly which curve corresponds to each variant.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Spark data-structure ranking is directly measured, not derived from fitted inputs or self-citations.

full rationale

The paper's central claim is an empirical performance comparison of three data-structure variants of RDD-Apriori (Section 5.2, Figs. 4(a-g)). The authors state explicitly in Section 4: 'We do not propose any new algorithm here, but do the analysis of execution time of RDD-Apriori for the three different underlying data structures.' No parameter is fitted to the evaluation data and then presented as a prediction; no formal derivation reduces an output to an input. The references to the authors' prior MapReduce study [19] and to Bodon [21] supply background and cross-platform interpretation, but the Spark-side ranking is produced by the experiments reported in this paper, so the self-citation is not load-bearing. The unreported heuristic settings of child_max_size and leaf_max_size and the absence of error bars are reproducibility and implementation-fairness concerns, not circularity: they do not make any claimed result equivalent to its inputs by construction. Accordingly, no circular step is identified.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The experiments rest on standard FIM machinery and existing data structures; no new entities are invented. The fragile parts of the ledger are the unreported hash tree configuration parameters and the unstated assumptions about implementation fidelity and measurement stability, all of which are domain assumptions rather than formal axioms. I list the hash tree parameters as free parameters because their heuristic setting directly shapes the measured speedup.

free parameters (2)
  • child_max_size (hash tree hashing table size) = not reported
    Section 4.2 says this parameter must be set heuristically for better performance; the per-dataset values are absent, so the baseline's behavior cannot be audited.
  • leaf_max_size (hash tree leaf threshold) = not reported
    Section 4.2 says this controls leaf-to-inner conversion and subset() cost; the values used in the experiments are not given.
assumptions (5)
  • domain assumption The RDD-HashTree-Apriori implementation is similar to YAFIM and the Trie and Hash Table Trie implementations faithfully realize Bodon's designs.
    Section 4.1 states the hash tree variant is similar to YAFIM with SPMF-derived code, while the Trie variants are described only at a high level and no source is provided, so fidelity to the cited designs is assumed.
  • domain assumption Single-run execution times on a 24-core local Spark cluster are representative of Spark cluster performance.
    Section 5.1 describes one workstation as a local Spark cluster; Section 5.2 reports point execution times with no repeated runs or variance, yet the conclusion is stated generally.
  • domain assumption The heuristic Hash Tree parameters were set to give the Hash Tree a fair comparison.
    Section 4.2 says child_max_size and leaf_max_size must be set heuristically; the chosen values are never reported, so fair treatment of the baseline is assumed.
  • domain assumption The seven FIMI and SPMF benchmark datasets are representative of Spark Apriori workloads.
    Table 1 lists standard benchmarks; the paper generalizes from them without a sampling or workload argument.
  • standard math The Apriori property: every subset of a frequent itemset is frequent, which justifies candidate pruning.
    Section 2.1 relies on this standard property (Agrawal and Srikant 1994) for candidate generation; it is a theorem of the support-count definition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Data Structure Perspective to the RDD-based Apriori Algorithm on Spark." pith.science (2026). https://pith.science/paper/F6DHSHVU

@misc{pith2026190801338,
  author       = {Pith},
  title        = {Pith review of: A Data Structure Perspective to the RDD-based Apriori Algorithm on Spark},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F6DHSHVU}},
  note         = {Machine review of arXiv:1908.01338}
}
read the original abstract

During the recent years, a number of efficient and scalable frequent itemset mining algorithms for big data analytics have been proposed by many researchers. Initially, MapReduce-based frequent itemset mining algorithms on Hadoop cluster were proposed. Although, Hadoop has been developed as a cluster computing system for handling and processing big data, but the performance of Hadoop does not meet the expectation for the iterative algorithms of data mining, due to its high I/O, and writing and then reading intermediate results in the disk. Consequently, Spark has been developed as another cluster computing infrastructure which is much faster than Hadoop due to its in-memory computation. It is highly suitable for iterative algorithms and supports batch, interactive, iterative, and stream processing of data. Many frequent itemset mining algorithms have been re-designed on the Spark, and most of them are Apriori-based. All these Spark-based Apriori algorithms use Hash Tree as the underlying data structure. This paper investigates the efficiency of various data structures for the Spark-based Apriori. Although, the data structure perspective has been investigated previously, but for MapReduce-based Apriori, and it must be re-investigated in the distributed computing environment of Spark. The considered underlying data structures are Hash Tree, Trie, and Hash Table Trie. The experimental results on the benchmark datasets show that the performance of Spark-based Apriori with Trie and Hash Table Trie are almost similar but both perform many times better than Hash Tree in the distributed computing environment of Spark.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum Computing and Data Processing for Frequent Itemset Mining

    cs.DB 2026-06 unverdicted novelty 7.0 of 10

    QFM mines frequent itemsets with quantum amplitude amplification over a pruned candidate subspace and a log-depth bit-parallel support oracle, claiming ~96% average runtime improvement over classical and hybrid baselines.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [1]

    In: 20th International Conference on Very Large Databases, pp

    Agrawal R, Srikant R (1994) Fast Algorithms for Mining Assoc iation Rules in Large Databases. In: 20th International Conference on Very Large Databases, pp. 487–499

    work page 1994

  2. [2]

    IEEE Transactions on Knowledge and Data Engineering 12(3):372-390

    Zaki M J (2000) Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering 12(3):372-390

    work page 2000

  3. [3]

    ACM SIGMOD Record 29(2):1-12

    Han J, Pei J, Yin Y (2000) Mining frequent patterns without candidate generation . ACM SIGMOD Record 29(2):1-12

    work page 2000

  4. [4]

    IEEE Concurrency 7(4):14-25

    Zaki M J (1999) Parallel and distributed association mining: a survey. IEEE Concurrency 7(4):14-25

    work page 1999

  5. [5]

    http://hadoop.apache.org

    Apache Hadoop. http://hadoop.apache.org. Accessed 28 May 2019 13

    work page 2019

  6. [6]

    https://hadoop.apache.org/docs/current/hadoop -project-dist/hadoop- hdfs/HdfsDesign.html

    HDFS Architecture . https://hadoop.apache.org/docs/current/hadoop -project-dist/hadoop- hdfs/HdfsDesign.html. Accessed 28 May 2019

    work page 2019

  7. [7]

    ACM Commun

    Dean J, Ghemawat S (2008) MapReduce: Simplified Data Processing on Large Clusters . ACM Commun. 51:107–113

    work page 2008

  8. [8]

    Review of Apriori Based Algorithms on MapReduce Framework

    Singh S, Garg R, Mishra P K (2017) Review of apriori based algorithms on mapreduce framework . arXiv preprint arXiv:1702.06284

    work page Pith review arXiv 2017

Show all 34 references
  1. [9]

    http://spark.apache.org

    Apache Spark. http://spark.apache.org. Accessed 28 May 2019

    2019

  2. [10]

    In: 2nd USENIX Conference on Hot Topics in Cloud Computing, pp

    Zaharia M, Chowdhury M, Franklin M J, Shenker S, Stoica I (2010) Spark: cluster computing with working sets. In: 2nd USENIX Conference on Hot Topics in Cloud Computing, pp. 10–10

    2010

  3. [11]

    In: 9th USENIX Conference on Networked Systems Design and Implementation, pp

    Zaharia M, Chowdhury M, Das T, Dave A, Ma J, McChauley M, Franklin M J, Shenker S, Stoica I (2012) Resilient distributed datasets: A fault -tolerant abstraction for in -memory cluster computing. In: 9th USENIX Conference on Networked Systems Design and Implementation, pp. 2-2

    2012

  4. [12]

    In: IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW), pp

    Qiu H, Gu R, Yuan C, Huang Y (2014) YAFIM: a parallel frequent itemset mining algorithm with spark. In: IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW), pp. 1664-1671

    2014

  5. [13]

    In: 8th ACM Ph

    Rathee S, Kaul M, Kashyap A (2015) R-Apriori: an efficient apriori based algorithm on spark. In: 8th ACM Ph. D. Workshop in Information and Knowledge Management, pp. 27-34

    2015

  6. [14]

    Journal of Big Data 5(1):6

    Rathee S, Kashyap A (2018) Adaptive-Miner: an efficient distributed association rule mining algorithm on Spark. Journal of Big Data 5(1):6

    2018

  7. [15]

    In: 9th IEEE International Conference on Frontier of Computer Science and Technology (FCST), pp

    Yang S, Xu G, Wang Z, Zhou F (2015) The parallel improved Apriori al gorithm research based on Spark. In: 9th IEEE International Conference on Frontier of Computer Science and Technology (FCST), pp. 354-359

    2015

  8. [16]

    Cluster Computing 18(4):1493-1501

    Zhang F, Liu M, Gui F, Shen W, Shami A, Ma Y (2015) A distributed frequent itemset mining algorithm using Spark for Big Data analytics. Cluster Computing 18(4):1493-1501

    2015

  9. [17]

    The Journal of Supercomputing 73(8):3652-3668

    Sethi K K, Ramesh D (2017) HFIM: a Spark-based hybrid frequent itemset mining algorithm for big data processing. The Journal of Supercomputing 73(8):3652-3668

    2017

  10. [18]

    In: 2nd IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), pp

    Shi X, Chen S, Yang H (2017) DFPS: Distributed FP-growth algorithm based on Spark. In: 2nd IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), pp. 1725-1731

    2017

  11. [19]

    International Journal of Computer Applications 128(9):45-51

    Singh S, Garg R, Mishra P K (2015) Performance Analysis of Apriori Algorithm with Different Data Structures on Hadoop Cluster. International Journal of Computer Applications 128(9):45-51

    2015

  12. [20]

    Mathematical and Computer Modelling 38(7):739-751

    Bodon F , Rónyai L (2003) Trie: an alternative data structure for data mining algorithms . Mathematical and Computer Modelling 38(7):739-751

    2003

  13. [21]

    In: IEEE ICDM workshop on frequent itemset mining implementations (FIMI’03), vol

    Bodon F (2003) A fast apriori implementation. In: IEEE ICDM workshop on frequent itemset mining implementations (FIMI’03), vol. 90

    2003

  14. [22]

    https://spark.apache.org/docs/latest/cluster-overview.html

    Cluster Overview. https://spark.apache.org/docs/latest/cluster-overview.html. Accessed 28 May 2019

    2019

  15. [23]

    https://spark.apache.org/docs/latest/rdd-programming-guide.html

    RDD Programming Guide. https://spark.apache.org/docs/latest/rdd-programming-guide.html. Accessed 28 May 2019

    2019

  16. [24]

    In: 21st ACM international conference on Information and knowledge management, pp

    Riondato M, DeBrabant J A, Fonseca R, Upfal E (2012) PARMA: A Parallel Randomized Algorithm for Approximate Association Rules Mining in MapReduce. In: 21st ACM international conference on Information and knowledge management, pp. 85-94

    2012

  17. [25]

    In: 6th ACM International Conference on Ubiquitous Information Management and Communication (ICUIMC ’12), Article 76 14

    Lin M-Y, Lee P-Y, Hsueh S-C (2012) Apriori-based Frequent Itemset Mining Algorithms on MapReduce. In: 6th ACM International Conference on Ubiquitous Information Management and Communication (ICUIMC ’12), Article 76 14

    2012

  18. [26]

    Computers & Electrical Engineering 67:348-364

    Singh S, Garg R, Mishra P K (2018) Performance optimization of MapReduce -based Apri ori algorithm on Hadoop cluster. Computers & Electrical Engineering 67:348-364

    2018

  19. [27]

    Cluster Computing 21(3):1507-1520

    Chon KW, Kim MS (2018) BIGMiner: a fast and scalable distributed frequent pattern miner for big data. Cluster Computing 21(3):1507-1520

    2018

  20. [28]

    In: IEEE International Conference on Big Data, pp

    Moens S, Aksehirli E, Goethals B (2013) Frequent Itemset Mining for Big Data . In: IEEE International Conference on Big Data, pp. 111–118

    2013

  21. [29]

    Springer LNCS: Database and Expert Systems Applications 9261:401-415

    Liu J, Wu Y, Zhou Q, Fung B C M, Chen F, Yu B (2015) Parallel Eclat for Opportunistic Mining of Frequent Itemsets. Springer LNCS: Database and Expert Systems Applications 9261:401-415

    2015

  22. [30]

    In: ACM Conference on Recommender System, pp

    Li H, Wang Y, Zhang D, Zhang M, Chang E Y (2008) PFP: Parallel FP -Growth for Query Recommendation. In: ACM Conference on Recommender System, pp. 107-114

    2008

  23. [31]

    In: IEEE Youth Conference on Information Computing and Telecommunications (YC - ICT), pp

    Zhou L, Zhong Z, Chang J, Li J, Huang J Z , Feng S (2010) Balanced pa rallel fp-growth with mapreduce. In: IEEE Youth Conference on Information Computing and Telecommunications (YC - ICT), pp. 243-246

    2010

  24. [32]

    IEEE Transactions on Systems, Man, and Cybernetics: Systems 46(3):313-325

    Xun Y, Zhang J, Qin X (2016) FiDoop: Parallel Mining of Frequent Itemsets Using MapReduce . IEEE Transactions on Systems, Man, and Cybernetics: Systems 46(3):313-325

    2016

  25. [33]

    In: 19th European Conference on Principles of Data Mining and Knowledge Discovery (PKDD 2016) Part III, Springer LNCS 9853:36-40

    Fournier-Viger P, Lin C W, Gomariz A, Gueniche T, Soltani A, Deng Z, Lam H T (2016) The SPMF Open-Source Data Mining Library Version 2 . In: 19th European Conference on Principles of Data Mining and Knowledge Discovery (PKDD 2016) Part III, Springer LNCS 9853:36-40

    2016

  26. [34]

    http://fimi.ua.ac.be/data

    Frequent Itemset Mining Dataset Repository. http://fimi.ua.ac.be/data. Accessed 28 May 2019

    2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.