{"id":"168bf8ea-c765-467d-bca5-d8a53638610c","arxiv_id":"1908.01338","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"On Spark, Apriori with a Trie or Hash Table Trie runs several times faster than with a Hash Tree, and the two Trie variants perform nearly identically.","lead":"The paper measured how the choice of internal data structure changes the speed of the Apriori frequent-itemset algorithm when it runs on Apache Spark. It found that Trie-based storage is several times faster than the widely used Hash Tree, and equally fast as a hashed Trie, across seven benchmark datasets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central speedup claim rests on an unverifiable comparison: the Hash Tree's heuristic parameters are never reported, no code is released, and timings are single-run, so the factor-of-six-to-eight gaps cannot be separated from tuning artifacts.","rationale":"The reader's verdict is CONDITIONAL with moderate confidence, and my reading supports that. The strongest claim is the measured performance ranking, and the weakest point is that the comparison does not isolate the data structure because the Hash Tree parameters are unreported and no artifacts are provided. This is not an internal inconsistency; the paper's own Section 4.2 calls the parameters heuristic, and the results are plausible and consistent with prior sequential and MapReduce findings. The absence of code, parameter values, and variance is a reproducibility problem rather than evidence of error, so it does not justify REJECT. It does justify requiring the artifacts before treating the ranking as established. The proposed check directly tests whether a plausible variation in the two Hash Tree parameters removes the claimed gap. No ad hominem is intended; the issue is evidential completeness.","tokens_in":10764,"tokens_out":3608,"duration_ms":40200,"concrete_test":"Obtain the authors' source and configuration files; independently rerun the comparison on T40I10D100K and BMS_WebView_2 at the lowest support reported in Fig. 4, using: (1) the authors' exact parameter settings, (2) a grid over child_max_size in {1,5,10,20} and leaf_max_size in {1,5,10,20}, and (3) at least five repeated runs per configuration with mean and standard deviation reported. If the Trie variants still outperform Hash Tree by a comparable margin across the grid, the ranking is robust to the heuristic parameter choice; if the gap collapses under reasonable settings, the headline claim is an artifact of parameterization.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the empirical ranking in Section 5.2: on all seven datasets the Trie-family variants outperform RDD-HashTree-Apriori by several times, while Trie and Hash Table Trie perform similarly. The paper explicitly states in Section 4.2 that Hash Tree has two parameters, child_max_size and leaf_max_size, 'that need to be set heuristically for the better performance', and that the Hash Tree code is taken from SPMF, whereas the Trie and Hash Table Trie variants are implemented in-house. But the parameter values used for each dataset are never given, the code is not released (Section 5.1 says only that the sources are Java-7), and Section 5.2 reports no repetitions or error bars. This makes the comparison underdetermined: if child_max_size/leaf_max_size were left at arbitrary defaults or chosen to favor the comparison, the reported 6-8x speedups could reflect mis-tuned Hash Tree rather than a property of the data structures. Because the paper's central conclusion is exactly that Spark-based Apriori should prefer Trie-family structures, the absence of these parameters and artifacts is load-bearing, not cosmetic. The direction of the effect is plausible and consistent with prior work, but the quantitative claim cannot be checked as presented.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10939,"tokens_out":3951,"duration_ms":39038,"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":[{"comment":"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.","section":"Section 4.2 and Section 5.2"},{"comment":"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.","section":"Section 5.2 and Figs. 4(a-g)"},{"comment":"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.","section":"Section 5.1"}],"minor_comments":[{"comment":"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'.","section":"Section 4.1 and Section 5.1"},{"comment":"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.","section":"Section 5.2"},{"comment":"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.","section":"Figs. 4(a-g)"}],"recommendation":"major_revision","confidential_remarks":"The main risk is reproducibility: without the Hash Tree parameter settings, repeated runs, and code release, the central empirical claim is difficult to verify. The direction of the result is plausible and consistent with prior work, so I do not see a need for rejection, but the requested additions are essential rather than cosmetic."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a modest, plausible empirical case study comparing three data structures for RDD-based Apriori on Spark. The headline result — Trie and Hash Table Trie beat Hash Tree by several-fold on seven datasets — is consistent and agrees with prior sequential and MapReduce findings. But the paper as written does not let you verify that the comparison is apples-to-apples, and the abstract overstates the field.\n\nWhat's actually new: the Spark-specific measurement. The techniques are all from Bodon, YAFIM, and the authors' own MapReduce paper, and the authors admit they propose no new algorithm. The contribution is a clean single-variable swap (candidate storage) inside one Spark implementation, and a consistent ranking across datasets. That is useful for practitioners choosing an implementation.\n\nSoft spots, in order. First, the Hash Tree parameters child_max_size and leaf_max_size are never reported. Section 4.2 says they are set heuristically; without the values, the speedup could be a mis-tuned baseline. Second, no code is released, so the in-house Trie implementations cannot be compared against the SPMF-derived Hash Tree for engineering quality. Third, timings are single-run, no error bars. Fourth, the abstract's claim that all Spark Apriori algorithms use Hash Tree is contradicted by the paper's own related work: R-Apriori uses a bloom filter, DFIMA a Boolean vector. That is sloppy framing, though it does not affect the measurements. The cross-platform explanation for why Hash Table Trie wins on MapReduce but ties with Trie on Spark is speculative but reasonable.\n\nThe central claim is credible in direction; the magnitude is not independently checkable. If the authors release code, parameter settings, and repeated-run statistics, the paper becomes a solid data point. As it stands, treat it as a suggestive case study, not a benchmark-grade result.\n\nIt deserves a serious referee because the question is real and the evidence, while incomplete, is honest and consistent. I would send it to review, with the expectation that the authors either supply artifacts or soften the quantitative claims.\n\nRegards.","headline":"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.","tokens_in":11556,"tokens_out":1504,"would_cite":false,"duration_ms":15578,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For Spark Apriori, replacing Hash Tree with Trie or Hash Table Trie speeds up runs by up to eight times on benchmark data.","keywords":["frequent itemset mining","Apriori","Apache Spark","RDD","Hash Tree","Trie","Hash Table Trie","data structures"],"falsifier":"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.","tokens_in":10498,"feed_emoji":"⚡","tokens_out":7228,"duration_ms":69432,"temperature":0.7,"pith_summary":"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.","feed_headline":"Trie structures beat Hash Tree for Apriori on Spark","feed_subtitle":"On all seven benchmark datasets, the Trie variants run many times faster than Hash Tree, and match each other.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines Apriori and the original Hash Tree-based candidate storage that the paper replaces.","marker":"[1]"},{"why":"Supplies the Spark-based Apriori design that the Hash Tree variant is modeled on and compared against.","marker":"[12]"},{"why":"Provides the earlier MapReduce-era data-structure comparison whose ranking the paper re-investigates on Spark.","marker":"[19]"},{"why":"Introduces the Trie as an alternative data structure for Apriori candidate generation and support counting.","marker":"[20]"},{"why":"Introduces the Hash Table Trie and reports its theoretical advantage but experimental failure in sequential Apriori.","marker":"[21]"},{"why":"Provides the Hash Tree implementation and several of the benchmark datasets used in the experiments.","marker":"[33]"},{"why":"Provides four of the seven benchmark datasets used in the experiments.","marker":"[34]"}],"fun_headline_variants":["Trie beats Hash Tree in Spark Apriori","Hash Tree trails Trie in Spark Apriori","Trie variants outperform Hash Tree on Spark","Spark Apriori: Trie outshines Hash Tree"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Trie beats Hash Tree in Spark Apriori","Hash Tree trails Trie in Spark Apriori","Trie variants outperform Hash Tree on Spark","Spark Apriori: Trie outshines Hash Tree"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000479,"raw_usage":{"total_tokens":2394,"prompt_tokens":987,"completion_tokens":1407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":1355}},"tokens_in":603,"tokens_out":1407,"duration_ms":11538,"temperature":1.0,"reasoning_tokens":1355,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:16:07.907983+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: 20th International Conference on Very Large Databases, pp","cited_arxiv_id":null,"evidence_quote":"Defines Apriori and the original Hash Tree-based candidate storage that the paper replaces."},{"cited_title":"In: IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW), pp","cited_arxiv_id":null,"evidence_quote":"Supplies the Spark-based Apriori design that the Hash Tree variant is modeled on and compared against."},{"cited_title":"International Journal of Computer Applications 128(9):45-51","cited_arxiv_id":null,"evidence_quote":"Provides the earlier MapReduce-era data-structure comparison whose ranking the paper re-investigates on Spark."},{"cited_title":"Mathematical and Computer Modelling 38(7):739-751","cited_arxiv_id":null,"evidence_quote":"Introduces the Trie as an alternative data structure for Apriori candidate generation and support counting."},{"cited_title":"In: IEEE ICDM workshop on frequent itemset mining implementations (FIMI’03), vol","cited_arxiv_id":null,"evidence_quote":"Introduces the Hash Table Trie and reports its theoretical advantage but experimental failure in sequential Apriori."},{"cited_title":"In: 19th European Conference on Principles of Data Mining and Knowledge Discovery (PKDD 2016) Part III, Springer LNCS 9853:36-40","cited_arxiv_id":null,"evidence_quote":"Provides the Hash Tree implementation and several of the benchmark datasets used in the experiments."},{"cited_title":"http://fimi.ua.ac.be/data","cited_arxiv_id":null,"evidence_quote":"Provides four of the seven benchmark datasets used in the experiments."}],"review_version":1}