make a comprehensive guide for us to understand the algorithm introduced by this paper, step by step with code:
"""
## 1 Introduction

Frequent itemset mining (FIM) plays an important role in many practical applications, including data mining \[[2](/article/10.1007/s41019-024-00241-2#ref-CR2 "Aggarwal CC (2015) Data mining—the textbook. Springer, Berlin"), [48](/article/10.1007/s41019-024-00241-2#ref-CR48 "Shah A, Halim Z (2019) On efficient mining of frequent itemsets from big uncertain databases. J Grid Comput 17(4):831–850"), [49](/article/10.1007/s41019-024-00241-2#ref-CR49 "Tang B, Zeng J, Tang Q, Yang C, Shen Q, Hou U L, Yan X, Zeng D (2022) CheetahKG: a demonstration for core-based top-k frequent pattern discovery on knowledge graphs. In 38th IEEE International Conference on Data Engineering, ICDE 2022, pp 3134–3137. IEEE")\], medical diagnosis \[[32](/article/10.1007/s41019-024-00241-2#ref-CR32 "Hirano S, Tsumoto S (2019) Mining frequent temporal patterns from medical data based on fuzzy ranged relations. In: 2019 IEEE international conference on big data (big data), pp 2654–2658. IEEE")\], spatio-temporal data analysis \[[9](/article/10.1007/s41019-024-00241-2#ref-CR9 "Atluri G, Karpatne A, Kumar V (2018) Spatio-temporal data mining: a survey of problems and methods. ACM Comput Surv 51(4):83:1-83:41")\] and bioinformatics \[[41](/article/10.1007/s41019-024-00241-2#ref-CR41 "Naulaerts S, Meysman P, Bittremieux W, Trung-Nghia V et al (2015) A primer to frequent itemset mining for bioinformatics. Briefings Bioinform 16(2):216–231")\]. Given a set of items, each transaction in the table contains a subset of the items. FIM discovers the sets of items (called _frequent itemsets_) that co-occur frequently among huge exploration space, which increases exponentially with respect to the number of the items. For each itemset, its support is the number of transactions containing it. FIM specifies a minimum support threshold to restrict the acquired itemsets whose supports are no less than the threshold.

Due to its practical importance, FIM has received extensive attentions since firstly proposed in \[[4](/article/10.1007/s41019-024-00241-2#ref-CR4 "Agrawal R, Imielinski T, Swami AN (1993) Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD international conference on management of data, pp 207–216"), [5](/article/10.1007/s41019-024-00241-2#ref-CR5 "Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of 20th international conference on very large data bases, pp 487–499")\], and many algorithms have been proposed \[[3](/article/10.1007/s41019-024-00241-2#ref-CR3 "Aggarwal CC, Han J (eds) (2014) Frequent pattern mining. Springer, Berlin"), [29](/article/10.1007/s41019-024-00241-2#ref-CR29 "Han J, Cheng H, Xin D, Yan X (2007) Frequent pattern mining: current status and future directions. Data Min Knowl Discov 15(1):55–86"), [31](/article/10.1007/s41019-024-00241-2#ref-CR31 "Han X, Liu X, Chen J, Lai G, Gao H, Li J (2019) Efficiently mining frequent itemsets on massive data. IEEE Access 7:31409–31421"), [40](/article/10.1007/s41019-024-00241-2#ref-CR40 "Luna JM, Fournier-Viger P, Ventura S (2019) Frequent itemset mining: a 25 years review. Wiley Interdiscip Rev Data Min Knowl Discov 9(6)")\]. However, it is found that the users normally are difficult to set the proper minimum support threshold to acquire the satisfied results \[[58](/article/10.1007/s41019-024-00241-2#ref-CR58 "Zhang S, Xindong W, Zhang C, Jingli L (2008) Computing the minimum-support for mining frequent patterns. Knowl Inf Syst 15(2):233–257")\], especially when without the relevant knowledge.

*   If the support threshold is set too high, very few (or even no) frequent itemsets can be discovered, and the users cannot find enough useful information for their decisions.
    
*   If the support threshold is set too small, a significantly large number of frequent itemsets will be generated, which not only degrades the efficiency seriously, but also overwhelms the users by enormous size of the results.
    

In order to obtain the reasonable size of frequent itemsets, one option is to try the different support thresholds over a certain range, which obviously is not acceptable due to high execution cost. Although the maximal and closed frequent itemset mining algorithms \[[11](/article/10.1007/s41019-024-00241-2#ref-CR11 "Burdick D, Calimlim M, Flannick J, Gehrke J, Yiu T (2005) MAFIA: a maximal frequent itemset algorithm. IEEE Trans Knowl Data Eng 17(11):1490–1504"), [28](/article/10.1007/s41019-024-00241-2#ref-CR28 "Halim Z, Ali O, Khan MG (2021) On the efficient representation of datasets as graphs to mine maximal frequent itemsets. IEEE Trans Knowl Data Eng 33(4):1674–1691"), [35](/article/10.1007/s41019-024-00241-2#ref-CR35 "Le T, Vo B (2015) An n-list-based algorithm for mining frequent closed patterns. Expert Syst Appl 42(19):6648–6657"), [52](/article/10.1007/s41019-024-00241-2#ref-CR52 "Vo B, Pham S, Le T, Deng Z-H (2017) A novel approach for mining maximal frequent patterns. Expert Syst Appl 73:178–186"), [57](/article/10.1007/s41019-024-00241-2#ref-CR57 "Zaki MJ, Hsiao C-J (2002) CHARM: an efficient algorithm for closed itemset mining. In: Proceedings of the Second SIAM international conference on data mining. SIAM, pp 457–473")\] are proposed to identify condensed representatives of frequent itemsets, they still need to specify the support threshold and cannot control the number of the required results.

For a better applicability of FIM, especially for the common users who are lack of the relevant knowledge, a parameter-light solution is preferred to let the data speak for themselves \[[33](/article/10.1007/s41019-024-00241-2#ref-CR33 "Keogh EJ, Lonardi S, Ratanamahatana C (2004) Towards parameter-free data mining. In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 206–215"), [54](/article/10.1007/s41019-024-00241-2#ref-CR54 "Xu T, Xu A, Mango J, Liu P, Ma X, Zhang L (2022) Efficient processing of top-k frequent spatial keyword queries. Sci Rep 12:7352")\]. Top-_k_ frequent itemset mining (Top-_k_ FIM) only asks the users to specify the number (_k_) of the required results directly, which is much comprehensible for the users, rather than the subtle support threshold.

### 1.1 Gap Analysis of Top-_k_ FIM

This paper focuses on top-_k_ FIM on massive data. Normally, massive data refer to data at massive scale. In this paper, we specify the scope of massive data as data set that cannot be maintained entirely on main memory when performing mining.

In order to understand the research question better, a gap analysis is performed first \[[12](/article/10.1007/s41019-024-00241-2#ref-CR12 "Channon DF, Sammut-Bonnici T (2015) Wiley encyclopedia of management—vol 12 strategic management. Wiley, New York")\], which assesses the differences between the actual performance and expected performance. On massive data, the memory cannot hold the entire data set and it will take a relatively long time to just scan the data set sequentially once. Under the circumstance, an efficient algorithm is expected to compute top-_k_ frequent itemsets on massive data quickly.

The existing top-_k_ FIM algorithms adopt apriori-like execution mode \[[15](/article/10.1007/s41019-024-00241-2#ref-CR15 "Chuang K-T, Huang J-L, Chen M-S (2008) Mining phtop-k frequent patterns in the presence of the memory constraint. VLDB J 17(5):1321–1344"), [23](/article/10.1007/s41019-024-00241-2#ref-CR23 "Fu AW-C, Kwong RW-w, Tang J (2000) Mining phN-most interesting itemsets. In: Proceedings of the 12th international symposium on foundations of intelligent systems, volume 1932 of LNCS, pp 59–67. Springer, Berlin")\] and FP-tree-based execution mode \[[14](/article/10.1007/s41019-024-00241-2#ref-CR14 "Cheung Y-L, Fu AW-C (2004) Mining frequent itemsets without support threshold: With and without item constraints. IEEE Trans Knowl Data Eng 16(9):1052–1069"), [45](/article/10.1007/s41019-024-00241-2#ref-CR45 "Pyun G, Yun U (2014) Mining top-k frequent patterns with combination reducing techniques. Appl Intell 41(1):76–98")\]. The former algorithms often need multiple scans on the table, which will incur a high I/O cost and a high computation cost for counting support on massive data. The latter algorithms have to construct the FP-tree first in memory by two passes of scan. Besides the relatively high I/O cost, it is unrealistic to assume that, on massive data, the complete FP-tree can be kept in the memory. In a word, the existing algorithms cannot deal with top-_k_ FIM on massive data efficiently.

Considering that the number _k_ of the results is relatively small, the solution with a high efficiency on massive data should involve the subset of the transactions and the subsets of items in the involved transactions, which are helpful for computing the top-_k_ frequent itemsets. This is the research idea of the algorithm proposed in this paper.

### 1.2 Our Contributions

This paper develops the prefix-based partitioning strategy given the specified order of the items. Each partition contains the transactions beginning with a certain item. By the prefix-based partitions, this paper devises PTF algorithm to mine top-_k_ frequent itemsets on massive data efficiently. PTF utilizes a min-heap _MH_ of size _k_ to maintain the _k_ itemsets discovered so far with the highest supports. Before processing the prefix-based partitions sequentially, PTF initializes _MH_ with the pre-constructed structures. Due to the prefix-based partitioning strategy, the itemsets beginning with a certain item can be generated separately in the corresponding partition. The partitions can be skipped directly, whose maximum supports of itemsets generated possibly are no larger than the minimum support of itemsets in _MH_. For the partitions to be processed, vertical mining is performed on the transactions of vertical representation by the high-support-first principle, and only a small fraction of the items are involved in the processing of the partitions. In this way, _PTF not only skips the entirely unnecessary partitions but also skips the unpromising items in the processed partitions_. Two improvements are utilized in PTF. One improvement introduces the _hybrid vertical storage mode_ to reduce the involved I/O cost furthermore. The tid-sets of the items can be stored in the form of tid-lists, dif-lists or bit-vectors adaptively. The corresponding operations are devised to intersect the tid-sets of items in the different forms. Another improvement exploits pruning strategy to reduce the number of the considered candidates by anti-monotone property. The extensive experiments are conducted on synthetic and real data sets. The experimental results show that, compared with the existing algorithms, PTF can achieve up to three orders of magnitude speedup ratio and involve two orders of magnitude less I/O cost.

The contributions of this paper are listed as follows:

*   This paper develops a novel prefix-partitioning-based PTF algorithm to mine top-_k_ frequent itemsets on massive data efficiently, which only retrieves a small fraction of transaction table for computing the results.
    
*   Hybrid vertical storage mode is proposed in this paper to keep the vertical representation of the items in one of three storage formats adaptively and reduce the involved I/O cost significantly.
    
*   Vertical mining is performed on the processed partitions of vertical representation, where the itemsets are generated with the high-support-first principle to speed up the in-memory computation.
    
*   The experimental results on synthetic and real-life data sets show that PTF outperforms the existing algorithms significantly.
    

The rest of the paper is organized as follows. We first survey the related works in Sect. [2](/article/10.1007/s41019-024-00241-2#Sec4), followed by preliminaries described in Sect. [3](/article/10.1007/s41019-024-00241-2#Sec7). The prefix-based partitioning is introduced in Sect. [4](/article/10.1007/s41019-024-00241-2#Sec10). In Sect. [5](/article/10.1007/s41019-024-00241-2#Sec14), we develop PTF algorithm, whose performance is evaluated in Sect. [6](/article/10.1007/s41019-024-00241-2#Sec22). The paper is concluded in Sect. [7](/article/10.1007/s41019-024-00241-2#Sec29).

## 2 Related Works

### 2.1 Frequent Itemset Mining

Given a support threshold _minsup_, FIM aims to discover the frequent itemsets among the universe of items, whose supports are greater or equal to _minsup_. By trading off in varying degrees the potential itemset number and the counting strategy, the existing FIM algorithms can be divided into three categories: level-wise approach, pattern-growth-based approach and vertical-format-based approach.

_Level-wise approach_. Apriori algorithm \[[5](/article/10.1007/s41019-024-00241-2#ref-CR5 "Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of 20th international conference on very large data bases, pp 487–499")\] adopts a level-wise execution mode. It uses the downward closure property to prune the search space. The frequent _b_\-itemsets in FbF\_b are used to generate the candidates Cb+1C\_{b + 1} of the frequent (b+1)(b + 1)\-itemsets, where _b_\-itemset is a set of items having _b_ items. By one pass of scan, the supports of candidates in Cb+1C\_{b + 1} are computed to find the frequent (b+1)(b + 1)\-itemsets Fb+1F\_{b + 1}. The process is repeated until Fb+1F\_{b + 1} is empty. Apriori algorithm often needs multiple scans over the table and incurs a high I/O cost on massive data, whose execution cost is analyzed in \[[20](/article/10.1007/s41019-024-00241-2#ref-CR20 "Dunkel B, Soparkar N (1999) Data organization and access for efficient data mining. In: Proceedings of the 15th international conference on data engineering, pp 522–529")\]. Many researchers study how to improve and extend the Apriori for a better performance. The improvements include partitioning strategy \[[47](/article/10.1007/s41019-024-00241-2#ref-CR47 "Savasere A, Omiecinski E, Navathe SB (1995) An efficient algorithm for mining association rules in large databases. In: Proceedings of 21th international conference on very large data bases. Morgan Kaufmann, pp 432–444")\], hashing technique \[[42](/article/10.1007/s41019-024-00241-2#ref-CR42 "Park JS, Chen M-S, Yu PS (1995) An effective hash based algorithm for mining association rules. In: Proceedings of the 1995 ACM SIGMOD international conference on management of data. ACM Press, pp 175–186")\], pre-computation \[[31](/article/10.1007/s41019-024-00241-2#ref-CR31 "Han X, Liu X, Chen J, Lai G, Gao H, Li J (2019) Efficiently mining frequent itemsets on massive data. IEEE Access 7:31409–31421")\] and distributed/parallel processing \[[7](/article/10.1007/s41019-024-00241-2#ref-CR7 "Apiletti D, Baralis E, Cerquitelli T, Garza P, Pulvirenti F, Venturini L (2017) Frequent itemsets mining for big data: a comparative analysis. Big Data Res 9:67–83")\].

_Pattern-growth-based approach_. Han et al. \[[30](/article/10.1007/s41019-024-00241-2#ref-CR30 "Han J, Pei J, Yin Y, Mao R (2004) Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Min Knowl Discov 8(1):53–87")\] propose FP-growth algorithm to mine the frequent patterns. FP-tree is a compact prefix-based trie structure to compress the transaction table. FP-growth starts with a frequent length-1 pattern as initial suffix pattern, and the set of frequent items co-occurring with the suffix pattern is extracted as conditional-pattern base, which is then constructed as conditional FP-tree. With the current suffix pattern and the conditional FP-tree, if the conditional FP-tree is not empty, FP-growth performs mining recursively. Grahne et al. \[[24](/article/10.1007/s41019-024-00241-2#ref-CR24 "Grahne G, Zhu J (2005) Fast algorithms for frequent itemset mining using fp-trees. IEEE Trans Knowl Data Eng 17(10):1347–1362")\] devise FPGrowth\* algorithm, which utilizes a special data structure FP-array to reduce the traversal time on FP-tree and speed up the FP-growth method significantly. Pei et al. \[[43](/article/10.1007/s41019-024-00241-2#ref-CR43 "Pei J, Han J, Lu H, Nishio S, Tang S, Yang D (2001) H-mine: hyper-structure mining of frequent patterns in large databases. In: Proceedings of the 2001 IEEE international conference on data mining, pp 441–448")\] devise H-mine based on a novel hyper-linked data structure H-struct to efficiently mine databases with different data characteristics. H-mine has very limited and precisely predictable space overhead, and can be scaled up to large database by partitioning. Liu et al. \[[39](/article/10.1007/s41019-024-00241-2#ref-CR39 "Liu G, Hongjun L, Lou W, Yabo X, Xu JY (2004) Efficient mining of frequent patterns using ascending frequency ordered prefix-tree. Data Min Knowl Discov 9(3):249–274")\] propose the AFOPT algorithm to mine the complete set of frequent patterns, which uses ascending frequency ordered prefix-tree to store the conditional databases, and the tree is traversed in top-down fashion.

_Vertical-format-based approach_. The level-wise approach and the pattern-growth-based approach discover the frequent itemsets by mining on the transaction table in the horizontal data format. Zaki \[[55](/article/10.1007/s41019-024-00241-2#ref-CR55 "Zaki MJ (2000) Scalable algorithms for association mining. IEEE Trans Knowl Data Eng 12(3):372–390")\] presents the ECLAT algorithm to mine the frequent itemsets on the vertical data format. Each itemset is associated with a TID list of transactions containing it. The frequent itemsets can be discovered by the intersection of the corresponding TID lists. According to Apriori property, the frequent (_b_ + 1)-itemsets can be generated by the previous generated frequent _b_\-itemsets. There are many extensions or improvements for the ECLAT algorithm by some novel vertical representations, including Diffset \[[56](/article/10.1007/s41019-024-00241-2#ref-CR56 "Zaki MJ, Gouda K (2003) Fast vertical mining using diffsets. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 326–335")\], N-list \[[19](/article/10.1007/s41019-024-00241-2#ref-CR19 "Deng Z-H, Wang Z, Jiang J-J (2012) A new algorithm for fast mining frequent itemsets using n-lists. Sci China Inf Sci 55(9):2008–2030")\], Nodeset \[[18](/article/10.1007/s41019-024-00241-2#ref-CR18 "Deng Z-H, Lv S-L (2014) Fast mining frequent itemsets using nodesets. Expert Syst Appl 41(10):4505–4512")\], DiffNodeset \[[17](/article/10.1007/s41019-024-00241-2#ref-CR17 "Deng Z-H (2016) DiffNodesets: an efficient structure for fast mining frequent itemsets. Appl Soft Comput 41:214–223")\] and NegNodeset \[[8](/article/10.1007/s41019-024-00241-2#ref-CR8 "Aryabarzan N, Minaei-Bidgoli B, Teshnehlab M (2018) negFIN: an efficient algorithm for fast mining frequent itemsets. Expert Syst Appl 105:129–143")\].

FIM often generates a large number of frequent itemsets, which makes it difficult for the users to obtain knowledge from them easily. In order to limit size of the output, the condensed representation of the frequent itemsets usually is required, such as maximal frequent itemsets \[[11](/article/10.1007/s41019-024-00241-2#ref-CR11 "Burdick D, Calimlim M, Flannick J, Gehrke J, Yiu T (2005) MAFIA: a maximal frequent itemset algorithm. IEEE Trans Knowl Data Eng 17(11):1490–1504"), [28](/article/10.1007/s41019-024-00241-2#ref-CR28 "Halim Z, Ali O, Khan MG (2021) On the efficient representation of datasets as graphs to mine maximal frequent itemsets. IEEE Trans Knowl Data Eng 33(4):1674–1691"), [52](/article/10.1007/s41019-024-00241-2#ref-CR52 "Vo B, Pham S, Le T, Deng Z-H (2017) A novel approach for mining maximal frequent patterns. Expert Syst Appl 73:178–186")\] and closed frequent itemsets \[[35](/article/10.1007/s41019-024-00241-2#ref-CR35 "Le T, Vo B (2015) An n-list-based algorithm for mining frequent closed patterns. Expert Syst Appl 42(19):6648–6657"), [57](/article/10.1007/s41019-024-00241-2#ref-CR57 "Zaki MJ, Hsiao C-J (2002) CHARM: an efficient algorithm for closed itemset mining. In: Proceedings of the Second SIAM international conference on data mining. SIAM, pp 457–473")\], which are much smaller than the frequent itemsets. However, the computation of the condensed representation still requires a specified _minsup_, which is tricky to find an appropriate value.

Besides, there also exist some approaches for mining frequent itemsets based on symbolic artificial intelligence \[[25](/article/10.1007/s41019-024-00241-2#ref-CR25 "Grossi V, Romei A, Turini F (2017) Survey on using constraints in data mining. Data Min Knowl Discov 31(2):424–464")\], which integrate the constraints and return the required itemsets satisfying the constraints. For the cases that the hard constraints do not guarantee the best results, the solutions with soft constraints are devised to entail the relaxing constraints \[[10](/article/10.1007/s41019-024-00241-2#ref-CR10 "Bistarelli S, Bonchi F (2007) Soft constraint based pattern mining. Data Knowl Eng 62(1):118–137"), [51](/article/10.1007/s41019-024-00241-2#ref-CR51 "Ugarte W, Boizumault P, Loudni S, Crémilleux B, Lepailleur A (2015) Soft constraints for pattern mining. J Intell Inf Syst 44(2):193–221")\]. The constraint programming can be embedded into itemset mining \[[26](/article/10.1007/s41019-024-00241-2#ref-CR26 "Guns T, Dries A, Nijssen S, Tack G, De Raedt L (2017) MiningZinc: a declarative framework for constraint-based mining. Artif Intell 244:6–29"), [27](/article/10.1007/s41019-024-00241-2#ref-CR27 "Guns T, Nijssen S, De Raedt L (2011) Itemset mining: a constraint programming perspective. Artif Intell 175(12–13):1951–1983")\]. The declarative constraint programming can be used to model and solve the constraint-based mining task. The constraint-based itemset mining algorithms mainly consider how to use declarative constraint programming to model and solve the issue of itemset mining. They provide another perspective for addressing itemset mining. However they do not give sufficient consideration to the efficient execution of algorithm. Comparatively, the main concern of this paper is how to design the algorithm and acquire the high execution efficiency.

### 2.2 Top-_k_ Frequent Itemset Mining

Top-_k_ FIM only needs to specify the number of the required results, a much more understandable and applicable parameter than the support threshold.

Given a upper bound _u_ of itemset size, Fu et al. \[[23](/article/10.1007/s41019-024-00241-2#ref-CR23 "Fu AW-C, Kwong RW-w, Tang J (2000) Mining phN-most interesting itemsets. In: Proceedings of the 12th international symposium on foundations of intelligent systems, volume 1932 of LNCS, pp 59–67. Springer, Berlin")\] propose the first algorithm _Itemset-Loop_ for mining _N_\-most interesting itemsets, the most frequent _N_ _b_\-itemsets for each _b_ (1≤b≤u1 \\le b \\le u). Initially, _Itemset-Loop_ sorts all 1-itemsets in the descending order of support, and reports the first _N_ 1-itemsets to be the _N_\-most interesting 1-itemsets P1P\_1. The candidate _b_\-itemsets CbC\_b (b≥2b \\ge 2) are generated from potential (b−1)(b - 1)\-itemsets in the way of the Apriori-gen algorithm \[[5](/article/10.1007/s41019-024-00241-2#ref-CR5 "Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of 20th international conference on very large data bases, pp 487–499")\]. PbP\_b is the _N_\-most interesting _b_\-itemsets in CbC\_b. Let supportbsupport\_{b} be the minimum support value of the _N_\-th _b_\-itemset in PbP\_b, and let lastsupportblastsupport\_b be the support of the last _b_\-itemset in PbP\_b. If lastsupport1≥supportblastsupport\_1 \\ge support\_b, P1P\_1 should be augmented by adding 1-itemsets with supports no less than supportbsupport\_b. P2P\_2 is updated correspondingly by including the 2-itemsets whose supports are no less than supportbsupport\_b. If lastsupport1≤supportblastsupport\_1 \\le support\_b, supportbsupport\_b will be compared with lastsupport2lastsupport\_2, …\\ldots, lastsupportb−1lastsupport\_{b - 1} successively with similar processing. _Itemset-Loop_ iterates the process similarly until PuP\_u is generated. _Itemset-iLoop_ improves _Itemset-Loop_ in the way that when generating PbP\_b, the loop back operation first examines (b−1)(b - 1)\-itemsets rather than loop backing to augmentation of the potential 1-itemsets.

Cheung et al. \[[14](/article/10.1007/s41019-024-00241-2#ref-CR14 "Cheung Y-L, Fu AW-C (2004) Mining frequent itemsets without support threshold: With and without item constraints. IEEE Trans Knowl Data Eng 16(9):1052–1069")\] also consider the _N_\-most interesting itemset mining. BOMO algorithm is first introduced which is based on FP-tree structure \[[30](/article/10.1007/s41019-024-00241-2#ref-CR30 "Han J, Pei J, Yin Y, Mao R (2004) Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Min Knowl Discov 8(1):53–87")\]. Initially, a complete FP-tree is built with all items in the database. Different from FP-growth algorithm, BOMO starts at the middle of the header table to achieve a good trade-off between the number of large conditional FP-trees and pruning power. From the middle position, BOMO first goes upward to the top and then from the (middle + 1) position down to the bottom of the header table. During the mining process, resultbresult\_b is used to maintain the current resulting set of the _N_\-most interesting _b_\-itemsets. The current support threshold δ\\delta can be kept for all the itemsets and be used to prune the conditional FP-trees. Since BOMO requires a complete FP-tree with all items, another algorithm LOOPBACK is devised to build a smaller initial FP-tree by an initial support threshold δ\>0\\delta > 0.

Chuang et al. \[[15](/article/10.1007/s41019-024-00241-2#ref-CR15 "Chuang K-T, Huang J-L, Chen M-S (2008) Mining phtop-k frequent patterns in the presence of the memory constraint. VLDB J 17(5):1321–1344")\] explore pure top-_k_ frequent patterns in the presence of the memory constraint. Different from the _N_\-most interesting itemset mining that retrieves the _N_ most frequent _b_\-itemsets (1≤b≤u)(1 \\le b \\le u) for an upper bound _u_, the pure top-_k_ frequent patterns refer to the _k_ most frequent itemsets without any constraint of item-lengths. It is noted that FP-tree-based solutions cannot be memory-constraint since the size of FP-tree is proportional to the database size, and MTK is developed in \[[15](/article/10.1007/s41019-024-00241-2#ref-CR15 "Chuang K-T, Huang J-L, Chen M-S (2008) Mining phtop-k frequent patterns in the presence of the memory constraint. VLDB J 17(5):1321–1344")\] as a level-wise-based search algorithm to compute pure top-_k_ frequent itemsets. In order to solve the problem of level-wise algorithms that generate a large number of candidates potentially, MTK adopts the δ\\delta\-stair search strategy. Initially, _k_ most frequent 1-itemsets and the hash table of all 2-itemsets in each transaction are maintained. The δ\\delta\-stair search shares McM\_c candidates equally to δ\\delta different itemset lengths. The upward δ\\delta\-stair search step and downward δ\\delta\-stair search step are adaptively switched until the results are found. The δ\\delta\-stair search combines the advantages of horizontal first search and vertical first search.

Pyun et al. \[[45](/article/10.1007/s41019-024-00241-2#ref-CR45 "Pyun G, Yun U (2014) Mining top-k frequent patterns with combination reducing techniques. Appl Intell 41(1):76–98")\] consider FP-tree-based top-_k_ frequent patterns with combination reducing technique. During the mining process on FP-tree, single-paths with many items are often generated, and a large number of combinations from the items will be generated in the single-paths. In order to reduce the pattern combinations, CRM algorithm defines strict closed pattern, i.e., all sub-patterns have the same support. The composite pattern is defined as the combination of the strict closed patterns with a general pattern. Initially CRM builds a global FP-tree containing all information of transaction table. CRM first selects the middle item in the header table of the FP-tree, generates the conditional database and tree, performs the mining operation. Top-_k_ list maintains the frequent patterns (or composite patterns) found in the mining steps. CRM then selects the items above and below the middle item, respectively, and processes them in the similar way as mentioned above. After the above mining step, CRM converts the composite patterns in top-_k_ list into the corresponding general patterns to release actual frequent patterns. CRMN algorithm is devised also to utilize multiple top-_k_ lists to mine _N_\-itemset top-_k_ patterns by a similar operation to CRM.

Top-rank-_k_ frequent itemset mining \[[21](/article/10.1007/s41019-024-00241-2#ref-CR21 "Fang G-D, Deng Z-H (2008) VTK: vertical mining of top-rank-k frequent patterns. In: Ma J, Yin Y, Yu J, Zhou S (eds) Fifth international conference on fuzzy systems and knowledge discovery, FSKD 2008, 18–20 October 2008, Jinan, Shandong, China, Proceedings, vol 2. IEEE Computer Society, pp 620–624")\] is very similar to top-_k_ FIM, and it returns the frequent itemsets whose ranks are not larger than _k_. Abdelaal et al. \[[1](/article/10.1007/s41019-024-00241-2#ref-CR1 "Abdelaal AA, Abed S, Alshayeji M, Al-laho M (2021) Customized frequent patterns mining algorithms for enhanced top-rank-k frequent pattern mining. Expert Syst Appl 169:114530")\] customize the three _N_\-list-based or Nodeset-based FIM algorithms to develop the latest customized top-rank-_k_ FIM algorithms (TK\_\\\_FIN, TK\_\\\_PrePost and TK\_\\\_PrePost+). The dynamic minimum support threshold strategy is used to increase the running minimum support threshold gradually. The transactions are first scanned to generate the 1-itemsets, which are inserted into the table structure TabK with _k_ entries. During the second scan, the transactions are retrieved and arranged in descending order of the supports of the items. The prefix tree is built on the retrieved transactions. The tree is scanned to generate the _N_\-lists or Nodesets of 2-itemsets. The rest of execution is performed in level-wise fashion. There are also other researches and extensions about top-_k_ FIM, such as top-_k_ FIM under differential privacy conditions for preserving privacy \[[36](/article/10.1007/s41019-024-00241-2#ref-CR36 "Lee J, Clifton CW (2014) Top-k frequent itemsets via differentially private FP-trees. In: The 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 931–940. ACM"), [38](/article/10.1007/s41019-024-00241-2#ref-CR38 "Liang W, Chen H, Zhang J, Zhao D, Li C (2020) An effective scheme for top-k frequent itemset mining under differential privacy conditions. Sci China Inf Sci 63(5)")\], top-_k_ FIM over data stream \[[13](/article/10.1007/s41019-024-00241-2#ref-CR13 "Chen H (2014) Mining top-k frequent patterns over data streams sliding window. J Intell Inf Syst 42(1):111–131")\], top-_k_ frequent-regular closed patterns \[[6](/article/10.1007/s41019-024-00241-2#ref-CR6 "Amphawan K, Lenca P (2015) Mining top-k frequent-regular closed patterns. Expert Syst Appl 42(21):7882–7894")\], top-_k_ frequent closed itemsets \[[53](/article/10.1007/s41019-024-00241-2#ref-CR53 "Wang J, Han J, Ying L, Tzvetkov P (2005) TFP: an efficient algorithm for mining top-k frequent closed itemsets. IEEE Trans Knowl Data Eng 17(5):652–664")\], top-_k_ closed sequential patterns \[[44](/article/10.1007/s41019-024-00241-2#ref-CR44 "Pham T-T, Do T, Nguyen A, Vo B, Hong T-P (2020) An efficient method for mining top-k closed sequential patterns. IEEE Access 8:118156–118163"), [50](/article/10.1007/s41019-024-00241-2#ref-CR50 "Tzvetkov P, Yan X, Han J (2005) TSP: mining top-phk closed sequential patterns. Knowl Inf Syst 7(4):438–457")\] and top-_k_ maximal frequent itemsets \[[46](/article/10.1007/s41019-024-00241-2#ref-CR46 "Salam A, Khayal MSH (2012) Mining top-k frequent patterns without minimum support threshold. Knowl Inf Syst 30(1):57–86")\].

In this paper, we focus on the pure top-_k_ frequent itemset mining. The latest top-_k_ FIM algorithms, including level-wise algorithm \[[15](/article/10.1007/s41019-024-00241-2#ref-CR15 "Chuang K-T, Huang J-L, Chen M-S (2008) Mining phtop-k frequent patterns in the presence of the memory constraint. VLDB J 17(5):1321–1344")\] and prefix-tree-based algorithm \[[45](/article/10.1007/s41019-024-00241-2#ref-CR45 "Pyun G, Yun U (2014) Mining top-k frequent patterns with combination reducing techniques. Appl Intell 41(1):76–98")\], require at least two passes of scan on T\\mathcal {T}. On massive data, they require a high execution cost to mine the top-_k_ frequent itemsets.

## 3 Preliminaries

In this section, the problem of top-_k_ **_f_**requent **_i_**temset **_m_**ining (top-_k_ FIM) is firstly defined in Sect. [3.1](/article/10.1007/s41019-024-00241-2#Sec8), and then problem analysis is provided in Sect. [3.2](/article/10.1007/s41019-024-00241-2#Sec9) to motivate an efficient algorithm. It is considered that an efficient algorithm should not retrieves all transactions but only involve the subsets of items in the required transactions useful for the mined results. The definitions of running minimum support and promising items are devised in Sect. [3.2](/article/10.1007/s41019-024-00241-2#Sec9) to determine the useful items when mining top-_k_ FIM.

### 3.1 Problem Definition

Let I\={x1,x2,…,xd}\\mathcal {I} = \\{ x\_1, x\_2, \\ldots , x\_d \\} be the set of all items, the itemset _X_ is a subset of I\\mathcal {I}, i.e., X⊆IX \\subseteq \\mathcal {I}, which is called _b_\-itemsets if |X|\=b|X| = b. Let T\={t1,t2,…,tn}\\mathcal {T} = \\{ t\_1, t\_2, \\ldots , t\_n \\} be the set of all transactions. ∀ti∈T\\forall t\_i \\in \\mathcal {T}, ti⊆It\_i \\subseteq \\mathcal {I}, and a unique transaction identifier (_tid_) is associated with tit\_i. For the itemset _X_, one of the most important property is its _support_, the number of the transactions in T\\mathcal {T} containing _X_. Mathematically, the support σ(X)\\sigma (X) of the itemset _X_ can be stated as σ(X)\=|{ti|X⊆ti,ti∈T}|\\sigma (X) = |\\{ t\_i | X \\subseteq t\_i, t\_i \\in \\mathcal {T} \\}|.

The itemset _X_ is called _frequent_ if its support is no less than the user-specified threshold _minsup_. As defined in Definition [1](/article/10.1007/s41019-024-00241-2#FPar1), FIM discovers all the frequent itemsets in T\\mathcal {T} given _minsup_.

### Definition 1

(_Frequent itemset mining_) Given T\\mathcal {T} and _minsup_, frequent itemset mining finds all itemsets _FI_ (FF\_{{{\\underline{\\varvec{{F}}}}}}requent II\_{{{\\underline{\\varvec{{I}}}}}}temsets), whose supports are no less than _minsup_, i.e., FI\={X|X⊆I,σ(X)≥minsup}FI = \\{ X | X \\subseteq \\mathcal {I}, \\sigma (X) \\ge minsup \\}.

Due to the difficulty of choosing the appropriate value of _minsup_, top-_k_ FIM is devised to find _k_ most frequent itemsets without the specification of _minsup_, as defined in Definition [2](/article/10.1007/s41019-024-00241-2#FPar2). The number _k_ of the required frequent itemsets is much easier to be understood compared with _minsup_. Let PI\\mathcal {P}\_\\mathcal {I} be the power set of I\\mathcal {I} excluding the empty set.

### Definition 2

(_Top-k frequent itemset mining_) Given T\\mathcal {T} and _k_, top-_k_ frequent itemset mining aims to find _k_ most frequent itemsets FIkFI\_k, where |FIk|\=k|FI\_k| = k and ∀X∈FIk\\forall X \\in FI\_k, ∀Y∈PI−FIk\\forall Y \\in \\mathcal {P}\_\\mathcal {I} - FI\_k, σ(X)≥σ(Y)\\sigma (X) \\ge \\sigma (Y).

**Fig. 1**

[![figure 1](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig1_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/1)

The illustration of transaction table in the running example

[Full size image](/article/10.1007/s41019-024-00241-2/figures/1)

### Example 1

As shown in Fig. [1](/article/10.1007/s41019-024-00241-2#Fig1), a running example is provided in this paper to illustrate the algorithm execution. There are 10 items x1,x2,…,x10x\_1, x\_2, \\ldots , x\_{10} and 12 transactions t1,t2,…,t12t\_1, t\_2, \\ldots , t\_{12} in the running example. We want top-8 FIM results. For example, given itemset {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\}, its support is 5since it is contained in five transactions t2,t5,t6,t7,t8t\_2, t\_5, t\_6, t\_7, t\_8.

Given I\\mathcal {I}, the number |PI||\\mathcal {P}\_\\mathcal {I}| of the possible itemsets is 2d−12^d - 1, which increases exponentially with respect to _d_. Here d\=|I|d = |\\mathcal {I}| is the number of the items. Obviously, the brute-force approach to search each possible itemset is practically impossible. Thus, all the solutions to solve FIM utilize the _downward closure property_ in Property [3.1](/article/10.1007/s41019-024-00241-2#FPar4) to reduce the search space significantly.

### Property 3.1

**(Downward closure property)** If an itemset _X_ is frequent, then all the subsets of _X_ are frequent.

### Property 3.2

**(Anti-monotone property)** Given an itemset _X_, for any subset _Y_ of _X_ (Y⊆XY \\subseteq X), we have σ(X)≤σ(Y)\\sigma (X) \\le \\sigma (Y).

Property [3.1](/article/10.1007/s41019-024-00241-2#FPar4) is very intuitive, ∀X⊆ti\\forall X \\subseteq t\_i, any subset of _X_ is contained in tit\_i also. The downward closure property can be rephrased as the anti-monotone property (Property [3.2](/article/10.1007/s41019-024-00241-2#FPar5)). The frequently used symbols in this paper are shown in Table [1](/article/10.1007/s41019-024-00241-2#Tab1).

**Table 1 Summary of symbols**

[Full size table](/article/10.1007/s41019-024-00241-2/tables/1)

### 3.2 Problem Analysis

On massive data, T\\mathcal {T} usually maintains a large number of transactions, tens of millions or even billions. In such a size of data, it will take a relatively long time just to scan it sequentially once, not to mention the involvement of expensive operations. Even though the mainstream machine has a larger and larger capacity of main memory, it is reasonable to consider that all transactions of T\\mathcal {T} cannot be maintained entirely in main memory.

The number _k_ of the required results typically is small (for example 10,000), since too many frequent itemsets provide excessive information that the users cannot find the useful knowledge easily. Evidently, among all the possible itemsets of size 2d−12^d - 1, the selected _k_ most frequent itemsets are much smaller, even negligible, to be more precise. Therefore, _the ideal case is to involve the subsets of items in the required transactions only_ which is helpful to compute FIkFI\_k.

Normally, itemset mining is considered to be a rather expensive task. An efficient implementation will be much helpful for the users. In our opinion, three important factors should be considered for designing an efficient top-_k_ FIM algorithm on massive data.

*   Although _minsup_ is not specified explicitly, it is used throughout the execution to discard the candidate itemsets by anti-monotone property. The existing algorithms set _minsup_ equal to zero initially, and gradually raise _minsup_ when more itemsets are generated. Some pre-computation is required to raise the initial _minsup_ properly at a low cost. This can improve the efficiency partly.
    
*   On massive data, the I/O cost of a single sequential scan is already relatively high. In order to achieve high efficiency, a _sub-linear algorithm_ is more desirable, which only involves a small fraction of the transactions. This requires designing the more resultful pruning strategy to reduce the number of the involved transactions.
    
*   Besides the pruning of the whole transactions, it is also desirable to narrow down the used items in each involved transaction correspondingly.
    

### Definition 3

(_Running minimum support_) During the execution of mining top-_k_ frequent itemsets, the support of the _k_th most frequent itemsets generated so far is referred as the rr\_{{{\\underline{\\varvec{r}}}}}unning mm\_{{{\\underline{\\varvec{m}}}}}inimum supsup\_{{{\\underline{\\varvec{sup}}}}}port (denoted by _rmsup_).

### Definition 4

(_Promising item_) ∀xi∈I\\forall x\_i \\in \\mathcal {I}, if σ(xi)\>rmsup\\sigma (x\_i) > rmsup, xix\_i is a promising item. Otherwise, xix\_i is unpromising and any superset of xix\_i cannot be the top-_k_ frequent itemsets.

**Fig. 2**

[![figure 2](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig2_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/2)

The illustration of promising items

[Full size image](/article/10.1007/s41019-024-00241-2/figures/2)

### Example 2

As depicted in Fig. [2](/article/10.1007/s41019-024-00241-2#Fig2), given _rmsup_ = 3, the promising items in the running example are x2,x4,x9,x10x\_2, x\_4, x\_9, x\_{10} since their supports are greater than 3.

In computing top-_k_ frequent itemsets, we only need to consider the promising items, and discard others directly. This is also the natural result of downward closure property. Clearly, the fewer the number of promising items, the lower computation cost.

∀xi,xj∈I(1≤i≠j≤d)\\forall x\_i, x\_j \\in \\mathcal {I} (1 \\le i \\ne j \\le d), σ(xixj)≤min{σ(xi),σ(xj)}\\sigma (x\_ix\_j) \\le \\min \\{\\sigma (x\_i), \\sigma (x\_j)\\} according to anti-monotone property. If we focus on the transactions containing xix\_i, a.k.a. the **_cov_**er set COV(T,xi)\={tj|xi∈tj,tj∈T(1≤j≤n)}COV(\\mathcal {T}, x\_i) = \\{ t\_j | x\_i \\in t\_j, t\_j \\in \\mathcal {T} (1 \\le j \\le n)\\}, every itemset generated from COV(T,xi)COV(\\mathcal {T}, x\_i) can be requested to contain xix\_i, since xix\_i occurs in every transaction in COV(T,xi)COV(\\mathcal {T}, x\_i). Any itemset containing xixjx\_i x\_j, if it exists, can be discovered in COV(T,xi)COV(\\mathcal {T}, x\_i). If σ(xixj)≤rmsup\\sigma (x\_i x\_j) \\le rmsup, the computation on COV(T,xi)COV(\\mathcal {T}, x\_i) to find top-_k_ frequent itemsets, which contain xix\_i definitely, does not need to consider xjx\_j. Since σ(xixj)≤σ(xj)\\sigma (x\_i x\_j) \\le \\sigma (x\_j), the much fewer promising items will be considered when processing COV(T,xi)COV(\\mathcal {T}, x\_i) compared with those when processing T\\mathcal {T}.

## 4 Prefix-Based Partitioning

Based on the analysis mentioned in Sect. [3.2](/article/10.1007/s41019-024-00241-2#Sec9), all itemsets can be generated by the cover set of individual items with fewer promising items involved. This section firstly devises a prefix-based partitioning strategy in Sect. [4.1](/article/10.1007/s41019-024-00241-2#Sec11) to split transaction table and materialize the cover sets of the items without the generation of duplicate itemsets. The space consumption of the prefix-based partitioning in direct form is analyzed in Sect. [4.2](/article/10.1007/s41019-024-00241-2#Sec12), showing that prefix-based partitioning is a workable strategy in space. Some useful structures are described in Sect. [4.3](/article/10.1007/s41019-024-00241-2#Sec13), which compute the supports of individual items in prefixed-based partitions to help item-level and partition-level pruning.

### 4.1 Partitioning Strategy

Given I\={x1,x2,…,xd}\\mathcal {I} = \\{ x\_1, x\_2, \\ldots , x\_d \\}, assume that there exists a total order among the items. Without loss of generality, let x1≺x2≺…≺xdx\_1 \\prec x\_2 \\prec \\ldots \\prec x\_d, the items are arranged in alphabetical order. The items in any itemsets are arranged in this order.

The prefix-based partitioning splits the table into _d_ partitions, in each of which the transactions _share the same prefix item_. ∀t∈T\\forall t \\in \\mathcal {T} and _t_ contains _b_ items, i.e., t\={x1′,x2′,…,xb′}t = \\{ x\_{1'}, x\_{2'}, \\ldots , x\_{b'} \\} and x1′≺x2′≺…≺xb′x\_{1'} \\prec x\_{2'} \\prec \\ldots \\prec x\_{b'}. ∀1≤j≤b\\forall 1 \\le j \\le b, the suffix items of _t_, {xj′,…,xb′}\\{ x\_{j'}, \\ldots , x\_{b'} \\}, are outputted to the partition Pj′P\_{j'}. The prefix-based partitions P1,P2,…,PdP\_1, P\_2, \\ldots , P\_d can be acquired by a sequential scan on T\\mathcal {T}.

For prefix-based partition Pi(1≤i≤d)P\_i (1 \\le i \\le d), ∀t∈T\\forall t \\in \\mathcal {T}, if xi∈tx\_i \\in t, the suffix items of _t_ beginning with xix\_i will be maintained in PiP\_i, otherwise, the items of _t_ will not appear in PiP\_i. In other words, PiP\_i can be uniquely determined given T\\mathcal {T}.

**Fig. 3**

[![figure 3](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig3_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/3)

The illustration of prefix-based transaction partitioning

[Full size image](/article/10.1007/s41019-024-00241-2/figures/3)

**Fig. 4**

[![figure 4](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig4_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/4)

The illustration of prefix-based partitions in the running example

[Full size image](/article/10.1007/s41019-024-00241-2/figures/4)

### Example 3

Figure [3](/article/10.1007/s41019-024-00241-2#Fig3) illustrates the prefix-based partitioning for transaction t2\={x1,x2,x9,x10}t\_2 = \\{x\_1, x\_2, x\_9, x\_{10}\\} in the running example. All prefix-based partitions are depicted in Fig. [4](/article/10.1007/s41019-024-00241-2#Fig4). There are 10 partitions since the running example has 10 items.

### Theorem 1

The prefix-based partitioning can generate complete and non-redundant itemsets.

### Proof

Given the prefix-based partition Pi(1≤i≤d)P\_i (1 \\le i \\le d), the itemsets with the prefix item xix\_i can be generated in PiP\_i according to the partitioning strategy. Let the possible itemsets generated in PiP\_i be GiG\_i, and any itemset possibly generated belongs to ⋃i\=1dGi\\bigcup \_{i = 1}^d G\_i. Besides, ∀Pi,Pj(1≤i≠j≤d)\\forall P\_i, P\_j (1 \\le i \\ne j \\le d), Gi∩Gj\=∅G\_i \\cap G\_j = \\emptyset, because they generate the itemsets with different prefix items. ◻\\square

For any itemset _X_ generated in PiP\_i, _it is a mandatory requirement that_ xi∈Xx\_i \\in X, because all transactions in PiP\_i begin with xix\_i. Theorem [1](/article/10.1007/s41019-024-00241-2#FPar10) proves that the prefix-based partitioning can generate complete and non-redundant itemsets. The support of any itemset _X_, whose first item is xix\_i, can be computed by the transactions in PiP\_i only. According to the analysis in Sect. [3.2](/article/10.1007/s41019-024-00241-2#Sec9), the number of the promising items when processing PiP\_i can be fewer significantly compared with that when processing T\\mathcal {T}.

### 4.2 The Space Consumption in Direct Form

In this part, we first analyze the space consumption of the prefix-based partitioning. Given T\\mathcal {T}, let average transaction width (i.e. average item number in a transaction) be _m_, each item is represented as an integer value (4 bytes). ∀t∈T\\forall t \\in \\mathcal {T} and t\={x1′,x2′,…,xm′}t = \\{ x\_{1'}, x\_{2'}, \\ldots , x\_{m'} \\}, ∀1≤j≤m\\forall 1 \\le j \\le m, (m−j+1)(m - j + 1) items {xj′,…,xm′}\\{ x\_{j'}, \\ldots , x\_{m'} \\} are written into the partition Pj′P\_{j'}. The total data size generated from _t_ is 4×(1+…+m)\=4×m×(m+1)24 \\times (1 + \\ldots + m) = 4 \\times \\frac{m \\times (m + 1)}{2} bytes in the prefix-based partitioning, it is m+12\\frac{m + 1}{2} times larger compared with the size of _t_.

Transaction table usually can be classified as sparse datasets and dense datasets, in terms of average transaction width and the number of items \[[16](/article/10.1007/s41019-024-00241-2#ref-CR16 "Dawar S, Goyal V, Bera D (2017) A hybrid framework for mining high-utility itemsets in a sparse transaction database. Appl Intell 47(3):809–827")\].

On _sparse dataset_, it usually has a small value of _m_ and a large value of _d_. Many practical applications, including the most popular area _market basket analysis_, generate sparse data set. For example, the supermarket sells a variety of goods (thousands or even larger), but each customer usually purchases very few of them in a transaction. The average basket size of Walmart is 11,[Footnote 1](#Fn1) chainstore data set and online retail data set have the average item counts of 7.23 and 4.37, respectively.[Footnote 2](#Fn2) In the prefix-based partitioning, the several-fold larger space consumption of the original data will be incurred for the sparse datasets. In return, orders of magnitude speedup can be achieved for our solution compared with the existing algorithms. This can be treated as a classical implementation of the idea that sacrifices space to improve efficiency.

On _dense dataset_, there is a small value of _d_, and the value of _m_ is relatively large. It is possible that the direct form of the prefix-based partitioning maintains one order of magnitude larger data than the original data. However, in this case, the value of _d_ is small, some transactions in the prefix-based partitions are identical, especially when the values of possible items are small. _Duplicate merging_ can be assisted in the prefix-based partitioning, the duplicate transactions can be merged to reduce the space.

Since our emphasis is to mine top-_k_ frequent itemsets efficiently by the prefix-based partitioning, the direct form of the partitioning is utilized here to clarify the description.

### 4.3 Some Pre-constructed Structures

Given the prefix-based partition Pi(1≤i≤d)P\_i (1 \\le i \\le d), whose transactions share the same prefix item xix\_i, the cc\_{{{\\underline{\\varvec{{c}}}}}}o-oo\_{{{\\underline{\\varvec{{o}}}}}}ccurrence nn\_{{{\\underline{\\varvec{{n}}}}}}umbers of the items in PiP\_i with xix\_i are recorded in the structure CoNiCoN\_i. CoNiCoN\_i in the memory is maintained in the form of _hash table_. Let CoNi(x)CoN\_i(x) be the co-occurrence number corresponding to the item _x_ in CoNiCoN\_i. ∀t∈Pi\\forall t \\in P\_i and t\={xi,y2,…,yb}(xi≺y2≺…≺yb)t = \\{ x\_i, y\_2, \\ldots , y\_b \\} (x\_i \\prec y\_2 \\prec \\ldots \\prec y\_b), firstly CoNi(xi)CoN\_i(x\_i) is increased by 1, and ∀2≤j≤b\\forall 2 \\le j \\le b, CoNi(yj)CoN\_i(y\_j) is increased by 1.

**Fig. 5**

[![figure 5](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig5_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/5)

The illustration of CoN structure in the running example

[Full size image](/article/10.1007/s41019-024-00241-2/figures/5)

All elements in CoN1,…,CoNdCoN\_1, \\ldots , CoN\_d are merged, let _CoN_(_itemset_, _count_) represent the merged structure. Specifically, for any element (item\=x,count\=c)(item = x, count = c) in CoNi(1≤i≤d)CoN\_i (1 \\le i \\le d), if (x\=xi)(x = x\_i), ({xi},c)(\\{ x\_i \\}, c) is added to _CoN_, otherwise ({xix},c)(\\{ x\_i x \\}, c) is added to _CoN_. The elements in _CoN_ are sorted in the descending order of _count_. The structure _CoN_ actually provides the supports of _d_ 1-itemsets and (d2)\\left( {\\begin{array}{c}d\\\\ 2\\end{array}}\\right) 2-itemsets, which will be utilized for PTF algorithm. Note that any 1-itemsets or 2-itemsets which are not kept explicitly in _CoN_ have count 0, indicating that they do not occur in the transactions. Let |_CoN_| denote the number of elements kept in _CoN_.

### Example 4

Given 10 items in the running example, CoN1,…,CoN10CoN\_1, \\ldots , CoN\_{10} are depicted in Fig. [5](/article/10.1007/s41019-024-00241-2#Fig5), which are merged and sorted in the descending order of count as CoN structure. In Fig. [5](/article/10.1007/s41019-024-00241-2#Fig5), only first 8 elements of CoN are listed, and other elements have count values no greater than 3.

## 5 PTF Algorithm

This section introduces PTF algorithm (PP\_{{{\\underline{\\varvec{{P}}}}}}refix-partitioning-based TT\_{{{\\underline{\\varvec{{T}}}}}}op-_k_ FF\_{{{\\underline{\\varvec{{F}}}}}}requent itemset mining) on massive data.

**Fig. 6**

[![figure 6](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig6_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/6)

The illustration of main component of PTF algorithm

[Full size image](/article/10.1007/s41019-024-00241-2/figures/6)

### 5.1 The Overview of the Algorithm

PTF processes the prefix-based partitions sequentially. The min heap for candidates and running minimum support _rmsup_, which are initialized by CoN structure, can be updated during its execution. By _rmsup_ and the maintained promising items, PTF can directly skip those partitions which cannot generate any top-_k_ frequent itemsets. This reduces the I/O cost and the computation cost effectively. When all partitions are processed or skipped, PTF discovers the mined results. The main component of PTF is described in Fig. [6](/article/10.1007/s41019-024-00241-2#Fig6).

**Algorithm 1**

[![figure a](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Figa_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/a)

PTF algorithm

[Full size image](/article/10.1007/s41019-024-00241-2/figures/a)

### 5.2 Basic Implementation

During its execution, PTF uses a **_m_**in **_h_**eap _MH_ of size _k_ (initially empty) to maintain the _k_ most frequent itemsets discovered so far. Let _MH_._min_ be the _k_th largest support of the itemsets in _MH_. The pseudo-code of PTF is listed in Algorithm 1.

_The initialization of rmsup_. As listed in line 1 to line 6 of Algorithm 1, initially, PTF reads the first _k_ elements in the structure _CoN_ and inserts them into _MH_, since the elements in _CoN_ are arranged in the descending order of their supports. If |CoN|≥k|CoN| \\ge k, rmsup\=MH.minrmsup = MH.min, otherwise, rmsup\=0rmsup = 0.

Note that all the itemsets in _MH_ currently are 1-itemsets or 2-itemsets. Let AR1,AR2,…,ARdAR\_1, AR\_2, \\ldots , AR\_d correspond to _d_ **_ar_**rays. ∀X∈MH\\forall X \\in MH, if X\={xi}X = \\{ x\_i \\} is a 1-itemset, xix\_i is inserted into ARiAR\_i, and if X\={xixj}X = \\{ x\_i x\_j \\} is a 2-itemset, xjx\_j is inserted into ARiAR\_i. The maintenance of the promising items is stated from line 7 to line 11 of Algorithm 1.

**Fig. 7**

[![figure 7](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig7_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/7)

The illustration of initializing rmsup in the running example

[Full size image](/article/10.1007/s41019-024-00241-2/figures/7)

**Fig. 8**

[![figure 8](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig8_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/8)

The illustration of promising items after rmsup initialization in the running example

[Full size image](/article/10.1007/s41019-024-00241-2/figures/8)

### Example 5

The initialization of rmsup in the running example is illustrated in Fig. [7](/article/10.1007/s41019-024-00241-2#Fig7), and initially _rmsup_ = 3 given _k_ = 8. With current _rmsup_, the promising items for each partition are listed in Fig. [8](/article/10.1007/s41019-024-00241-2#Fig8).

After the initialization of _rmsup_, PTF deals with the partitions one by one (from line 12 to line 21 of Algorithm 1). ∀1≤i≤d\\forall 1 \\le i \\le d, let PiP\_i be the currently processed partition. PTF first iterates through the elements in ARiAR\_i. Due to anti-monotone property, σ(xi)\\sigma (x\_i) is the maximum support that all itemsets generated in PiP\_i can have. If σ(xi)≤rmsup\\sigma (x\_i) \\le rmsup, PiP\_i cannot generate any top-_k_ frequent itemsets, and there is no meaning of checking the remaining items in ARiAR\_i (line 14). Here, PTF clears all elements in ARiAR\_i and terminates the iteration (line 15). Otherwise, ∀xj∈ARi−xi\\forall x\_j \\in AR\_i - x\_i, if σ(xixj)≤rmsup\\sigma (x\_i x\_j) \\le rmsup, xjx\_j is removed from ARiAR\_i (line 16 and line 17)). At the end of the iteration on ARiAR\_i, _the remaining elements in_ ARiAR\_i _correspond to the promising items in_ PiP\_i. Actually, ARiAR\_i contains the |ARi||AR\_i| items in PiP\_i with the largest supports. The items in ARiAR\_i are sorted in the specified order.

_The case of skipping partition_. Proved by Theorem [2](/article/10.1007/s41019-024-00241-2#FPar18), if |ARi|≤2|AR\_i| \\le 2, PTF does not need to process PiP\_i any more, it can skip PiP\_i directly and proceed with the next partition (line 18 and line 19 of Algorithm 1).

Note that, in order to improve the readability of the paper, the theoretical contents in this section are slit from the algorithmic description, and the relevant theorems and their proofs are put in Sect. [5.5](/article/10.1007/s41019-024-00241-2#Sec21).

### Example 6

As shown in Fig. [5](/article/10.1007/s41019-024-00241-2#Fig5), with the initialized _rmsup_ (3), PTF does not need to process P1,P3,P5,P6,P7,P8P\_1, P\_3, P\_5, P\_6, P\_7, P\_8 since their maximum supports are no greater than current _rmsup_. And PTF processes P2,P4,P9,P10P\_2, P\_4, P\_9, P\_{10} sequentially. Firstly, P2P\_2 is dealt with.

If there are at least three promising items in ARiAR\_i (i.e., |ARi|≥3|AR\_i| \\ge 3), PTF deals with PiP\_i to discover the possible top-_k_ frequent itemsets (line 21 of Algorithm 1). The pseudo-code of processing single partition is listed in Algorithm 2.

Since only the promising items in ARiAR\_i are useful for the mining process, PTF needs to retrieve the required data. Therefore, the transactions in PiP\_i are kept in vertical storage mode. For an item _x_ in PiP\_i, the tid-set of _x_ is a set of transaction identifiers of the transactions in PiP\_i containing _x_. The tid-sets of the items (excluding xix\_i) are arranged _in the descending order of supports of the items_. The tid-set of xix\_i is not kept explicitly since all transactions in PiP\_i contain xix\_i. Due to xi∈ARix\_i \\in AR\_i, when processing PiP\_i, PTF only retrieves _the tid-sets of the first_ (|ARi|−1)(|AR\_i| - 1) _items_ in PiP\_i. Here, the case of the items with the equal supports should be considered to guarantee that PTF obtains the tid-sets of items in ARiAR\_i.

**Fig. 9**

[![figure 9](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig9_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/9)

The illustration of vertical storage mode of partition P2P\_2. The tid-set of x2x\_2 is not maintained explicitly

[Full size image](/article/10.1007/s41019-024-00241-2/figures/9)

### Example 7

Figure [9](/article/10.1007/s41019-024-00241-2#Fig9) illustrates the vertical storage mode of the current P2P\_2, the tid-sets of the items are arranged in the descending order of supports. Since the promising items of P2P\_2 are x2,x9,x10x\_2, x\_9, x\_{10} (Fig. [8](/article/10.1007/s41019-024-00241-2#Fig8)), only the tid-sets of x10x\_{10} and x9x\_9 are retrieved.

PTF utilizes a hh\_{{{\\underline{\\varvec{{h}}}}}}ash tt\_{{{\\underline{\\varvec{{t}}}}}}able _HT_ to maintain the tid-sets of the itemsets during the processing of PiP\_i. At first, (|ARi|−1)(|AR\_i| - 1) 2-itemsets, xixjx\_i x\_j (xj∈ARi−xix\_j \\in AR\_i - x\_i), and their tid-sets are kept in _HT_ (line 2 and line 3 of Algorithm 2). Given the itemset _X_ which is in _HT_, _HT_(_X_) corresponds to the tid-sets of _X_. Besides, a priority **_q_**u**_e_**ue _QE_ is exploited to store the itemsets and explore them by the high-support-first principle (line 4 of Algorithm 2). The root element has the maximum support in _QE_. Let _QE_._max_ be the largest supports among itemsets in _QE_. At the beginning, (|ARi|−1)(|AR\_i| - 1) 2-itemsets xixjx\_i x\_j (xj∈ARi−xix\_j \\in AR\_i - x\_i) are maintained in _QE_.

_The overview of execution_. From the itemsets in _QE_, PTF generates the longer itemsets and their corresponding tid-sets in the way of the _growth of the itemsets_ described below until the _termination condition_ is satisfied (from line 5 to line 14 of Algorithm 2).

**Algorithm 2**

[![figure b](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Figb_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/b)

ProcessSglPartition

[Full size image](/article/10.1007/s41019-024-00241-2/figures/b)

_The growth of the itemsets_. Every time PTF needs to explore more itemsets, the root element XrtX\_{rt} in _QE_ is removed (line 6 of Algorithm 2). Within the loop from line 8 to line 14, we have σ(Xrt)\>rmsup\\sigma (X\_{rt}) > rmsup. Let XrtX\_{rt} be in the form of Xy1X y\_{1}, where _X_ is the prefix items of XrtX\_{rt} without the last item y1y\_1. If |Xrt|≥3|X\_{rt}| \\ge 3, PTF first updates _MH_ by removing its root element and inserting XrtX\_{rt} into it (line 8 of Algorithm 2). Then more itemsets will be generated by expanding XrtX\_{rt} with each of the items in ARiAR\_i after y1y\_1 (from line 9 to line 14 of Algorithm 2). Let y1y\_1 be the _a_th item in ARiAR\_i. ∀y2∈ARi(a+1,…,|ARi|)\\forall y\_2 \\in AR\_i(a + 1, \\ldots , |AR\_i|), PTF first checks whether the itemset Xy2X y\_2 is kept in _HT_.

*   If HT(Xy2)≠nullHT(X y\_2) \\ne null, the tid-set HT(Xy1)HT(X y\_1) of Xy1X y\_1 and the tid-set HT(Xy2)HT(X y\_2) of Xy2X y\_2 are intersected to generate the tid-set of the itemset Xy1y2X y\_1 y\_2 (line 11). If σ(Xy1y2)\>rmsup\\sigma (X y\_1 y\_2) > rmsup, PTF keeps Xy1y2X y\_1 y\_2 and its tid-sets in _HT_, and also inserts it in _QE_ for the further exploration (line 13 and line 14 of Algorithm 2).
    
*   Otherwise, HT(Xy2)HT(X y\_2) = null, as proved in Theorem [3](/article/10.1007/s41019-024-00241-2#FPar20), σ(Xy2)≤rmsup\\sigma (X y\_2) \\le rmsup, PTF proceeds with the next item in ARiAR\_i to expand XrtX\_{rt}.
    

In a word, PTF explores the itemsets in the enumeration space by _hybrid search strategy_, combining depth-first search and level-wise search.

_Termination condition_. If the support of XrtX\_{rt} is no greater than _rmsup_, i.e., QE.max≤rmsupQE.max \\le rmsup, as proved in Theorem [4](/article/10.1007/s41019-024-00241-2#FPar22), the processing of PiP\_i can terminate and PTF continues to deal with the next partition. The condition is checked in line 5 of Algorithm 2.

**Fig. 10**

[![figure 10](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig10_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/10)

The illustration of vertical storage mode of partition P2P\_2. The tid-set of x2x\_2 is not maintained explicitly

[Full size image](/article/10.1007/s41019-024-00241-2/figures/10)

### Example 8

The processing of P2P\_2 is depicted in Fig. [10](/article/10.1007/s41019-024-00241-2#Fig10). The tid-sets of {x2,x9}\\{x\_2, x\_9\\} and {x2,x10}\\{x\_2, x\_{10}\\} are maintained in hash table _HT_. The two 2-itemsets are filled into max heap _QE_. Current root element of _QE_ is {x2,x10}\\{ x\_2, x\_{10} \\}, which is removed first. Since its size is less than 3 and x10x\_{10} is the last promising item of P2P\_2, {x2,x10}\\{x\_2, x\_{10}\\} cannot update _MH_ and add larger itemsets to _QE_. Next, the current root element {x2,x9}\\{x\_2, x\_9\\} of _QE_ is removed. {x2,x9}\\{ x\_2, x\_9 \\} can be extended by adding x10x\_{10}. The tid-set of {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\} is generated by intersecting the tidsets of {x2,x9}\\{x\_2, x\_9\\} and {x2,x10}\\{x\_2, x\_{10}\\}, and the support of {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\} is 5. Given the current rmsup 3, {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\} is added into _QE_ and its tid-set is kept in _HT_. The current root {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\} of _QE_ is removed, its size is larger than 2 and support is greater than _rmsup_. Min heap _MH_ is updated by removing it root {x2,x4}\\{x\_2, x\_4\\} and inserting {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\}. The current _rmsup_ is updated to 4. {x2,x9,x10}\\{ x\_2, x\_9, x\_{10} \\} cannot be extended since x10x\_{10} is the last promising item of P2P\_2. Then _QE_ is empty and the processing of P2P\_2 is complete. For the remaining partitions P3,…,P10P\_3, \\ldots , P\_{10}, the maximum support of possibly generated itemsets is less than 4, PTF directly skips them and reports the mined results.

### 5.3 Improvement 1: Hybrid Vertical Storage Mode

At dealing with PiP\_i, ARiAR\_i corresponds to the |ARi||AR\_i| items with the largest supports, and PTF needs to retrieve the tid-sets of the first (|ARi|−1)(|AR\_i| - 1) items into memory. Although this discards the irrelevant items directly, the required data volume is still considerable since the loaded items are the (|ARi|−1)(|AR\_i| - 1) most frequent items (except xix\_i). Improvement 1 introduces hybrid vertical storage mode for the prefix-based partitions to reduce the involved I/O cost in the execution.

#### 5.3.1 Storage Mode

∀1≤i≤d\\forall 1 \\le i \\le d, let nin\_i be the number of transactions in the partition PiP\_i. Since the support of any itemset beginning with xix\_i can be computed by PiP\_i only, ∀1≤a≤ni\\forall 1 \\le a \\le n\_i, the _a_th transaction in PiP\_i is assigned with a unique identifier (_tid_) _a_. The transactions in PiP\_i are stored in the vertical format. That is, each item xj(i+1≤j≤d)x\_j (i + 1 \\le j \\le d) is associated with a _tid-set_, representing the tids of the transactions containing it. Since all transactions in PiP\_i share the prefix item xix\_i, we do not keep its tid-set. _The tid-sets for the items (excluding_ xix\_i_) in_ PiP\_i _are arranged in the descending order of the supports of the items_.

For the item xjx\_j, its tid-set can be maintained in one of the three storage mode (_tid-list_, _dif-list_, _bit-vector_) depending on three **_s_**i**_z_**e values, SZtidlist\=4×|L(xj)|SZ\_{tidlist} = 4 \\times |L(x\_j)|, SZdiflist\=4×(ni−|L(xj)|)SZ\_{diflist} = 4 \\times \\left( n\_i - |L(x\_j)|\\right) and SZbv\=⌈ni8⌉SZ\_{bv} = \\lceil \\frac{n\_i}{8} \\rceil.

*   The first value is the size of tid-list L(xj)L(x\_j), which is a list to keep the tids of the transactions containing xjx\_j.
    
*   The second value is the size of the dif-list D(xj)D(x\_j), i.e. {1,2,…,ni}−L(xj)\\{1,2, \\ldots , n\_i\\} - L(x\_j), which is a list to keep the tids of the transactions not containing xjx\_j.
    
*   The third value is the size of the bit-vector BV(xj)BV(x\_j) of nin\_i bits. The _a_th bit in BV(xj)BV(x\_j) is 1 if the _a_th transaction contains xjx\_j, otherwise, the _a_th bit in BV(xj)BV(x\_j) is 0.
    

Hybrid storage mode selects the corresponding storage mode with the minimum size. Storage schema of tid-set of xjx\_j is (xj,flag,DS,L(xj)|D(xj)|BV(xj))\\left( x\_j, flag, DS, L(x\_j) | D(x\_j) | BV(x\_j)\\right), where xjx\_j is the item, flag(−1,0,1)flag (-1, 0, 1) indicates the tid-set is stored as tid-list L(xj)L(x\_j), dif-list D(xj)D(x\_j) or bit-vector BV(xj)BV(x\_j), and _DS_ is **_d_**ata **_s_**ize (in bytes) of tid-set in the given format.

**Fig. 11**

[![figure 11](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig11_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/11)

The illustration of hybrid vertical storage

[Full size image](/article/10.1007/s41019-024-00241-2/figures/11)

### Example 9

Figure [11](/article/10.1007/s41019-024-00241-2#Fig11) illustrates an example of hybrid vertical storage for partition PiP\_i, which has 1000 transactions. For item xi+j1x\_{i + j\_1} whose tid-set contains 997 tids, D(xi+j1)D(x\_{i + j\_1}) occupies the smallest space. For item xi+j2x\_{i + j\_2} whose tid-set includes 500 tids, BV(xi+j2)BV(x\_{i + j\_2}) is the structure with the smaller space compared with other two forms. For item xi+j3x\_{i + j\_3} whose tid-set keeps 4 tids, the direct tid-list form is the best choice.

Next we analyze the effect of hybrid vertical storage mode. Given a partition PiP\_i, there are (d−i)(d - i) tid-sets for the possible items xi+1,…,xdx\_{i + 1}, \\ldots , x\_d. For the sake of discussion, suppose that the supports of σ(xixj)\\sigma (x\_i x\_j) (i+1≤j≤d)(i + 1 \\le j \\le d) are uniformly distributed over the range \[0,α×ni\]\[0, \\alpha \\times n\_i\] and σ(xixi+1)\>σ(xixi+2)\>…\>σ(xixd)\\sigma (x\_i x\_{i + 1})> \\sigma (x\_i x\_{i + 2})> \\ldots > \\sigma (x\_i x\_d), where α(0<α≤1)\\alpha (0 < \\alpha \\le 1) is the parameter depending on the characteristics of the table. ∀(i+1)≤j≤d\\forall (i + 1) \\le j \\le d, σ(xixj)\=d−j+1d−i×α×ni\\sigma (x\_i x\_j) = \\frac{d - j + 1}{d - i} \\times \\alpha \\times n\_i, SZtidlist\=4×d−j+1d−i×α×niSZ\_{tidlist} = 4 \\times \\frac{d - j + 1}{d - i} \\times \\alpha \\times n\_i, SZdiflist\=4×(1−d−j+1d−i×α)×niSZ\_{diflist} = 4 \\times (1 - \\frac{d - j + 1}{d - i} \\times \\alpha ) \\times n\_i and SZbv\=⌈ni8⌉SZ\_{bv} = \\lceil \\frac{n\_i}{8} \\rceil. If SZbv≤min(SZtidlist,SZdiflist)SZ\_{bv} \\le \\min (SZ\_{tidlist}, SZ\_{diflist}), i.e. 132≤d−j+1d−i×α≤3132\\frac{1}{32} \\le \\frac{d - j + 1}{d - i} \\times \\alpha \\le \\frac{31}{32}, the tid-set of xjx\_j is kept in bit-vector. If SZtidlist≤min(SZdiflist,SZbv)SZ\_{tidlist} \\le \\min (SZ\_{diflist}, SZ\_{bv}), i.e., d−j+1d−i×α≤132\\frac{d - j + 1}{d - i} \\times \\alpha \\le \\frac{1}{32}, the tid-set of xjx\_j is kept in tid-list. If SZdiflist≤min(SZtidlist,SZbv)SZ\_{diflist} \\le \\min (SZ\_{tidlist}, SZ\_{bv}), i.e., d−j+1d−i×α≥3132\\frac{d - j + 1}{d - i} \\times \\alpha \\ge \\frac{31}{32}, the tid-set of xjx\_j is kept in dif-list. According to the computation formula above, Fig. [12](/article/10.1007/s41019-024-00241-2#Fig12) compares the space consumption for loading the required tid-sets between hybrid vertical storage mode and complete tid-list format from the aspects of varying promising item numbers, α\\alpha values and (d−i)(d - i) values, respectively. As depicted in Fig. [12](/article/10.1007/s41019-024-00241-2#Fig12), by utilizing hybrid vertical storage mode, PTF can reduce the I/O cost of loading the tid-sets of promising items by an order of magnitude, which also is verified in our experiments. It should be noted that, the results in Fig. [1](/article/10.1007/s41019-024-00241-2#Fig1) are not targeted to the specific type of data set, but they illustrate the general effect of the proposed storage mode under the above assumption. The actual effect in the real-life data sets of different characteristics is provided in the experimental section.

**Fig. 12**

[![figure 12](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig12_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/12)

The space comparison between hybrid vertical storage mode and complete tid-list format

[Full size image](/article/10.1007/s41019-024-00241-2/figures/12)

#### 5.3.2 The Intersection of the Tid-Sets

Since the tid-sets of the items in PiP\_i are kept in three data formats: tid-lists, dif-lists and bit-vectors, the intersection of the tid-sets should be processed in six different cases.

**_Case 1_**: _the intersection of tid-list and tid-list_.

The intersection in case 1 is simple. Given two itemsets Xy1Xy\_1 and Xy2Xy\_2, their tid-lists are L(Xy1)L(Xy\_1) and L(Xy2)L(Xy\_2), respectively. Since tid-list maintains the tids in the ascending order, the tid-list of Xy1y2X y\_1 y\_2 is L(Xy1)∩L(Xy2)L(Xy\_1) \\cap L(Xy\_2) which can be computed directly by binary merging. σ(Xy1y2)\=|L(Xy1y2)|\\sigma (X y\_1 y\_2) = |L(X y\_1 y\_2)|.

**_Case 2_**: _the intersection of dif-list and dif-list_.

Given two itemsets Xy1Xy\_1 and Xy2Xy\_2, their dif-lists are D(Xy1)D(Xy\_1) and D(Xy2)D(Xy\_2), respectively. D(Xy1)\={1,2,…,ni}−L(Xy1)D(X y\_1) = \\{ 1, 2, \\ldots , n\_i \\} - L(X y\_1) and D(Xy2)\={1,2,…,ni}−L(Xy2)D(X y\_2) = \\{ 1, 2, \\ldots , n\_i \\} - L(X y\_2). ∀a1∈D(Xy1)\\forall a\_1 \\in D(Xy\_1), the transaction with tid a1a\_1 does not contain Xy1X y\_1, and ∀a2∈D(Xy2)\\forall a\_2 \\in D(Xy\_2), the transaction with tid a2a\_2 does not contain Xy2X y\_2. Obviously, ∀a∈D(Xy1)∪D(Xy2)\\forall a \\in D(X y\_1) \\cup D(X y\_2), the transaction with tid _a_ does not contain Xy1X y\_1 or Xy2X y\_2. The intersection of the tid-sets of Xy1Xy\_1 and Xy2Xy\_2 is L(Xy1)∩L(Xy2)L(Xy\_1) \\cap L(Xy\_2), which corresponds to the transactions contains both Xy1X y\_1 and Xy2X y\_2, we have:

L(Xy1y2)\=L(Xy1)∩L(Xy2)\={1,2,…,ni}−D(Xy1)∪D(Xy2)D(Xy1y2)\={1,2,…,ni}−L(Xy1y2)\=D(Xy1)∪D(Xy2)

\\begin{aligned} \\begin{aligned} L(X y\_1 y\_2)&= L(Xy\_1) \\cap L(Xy\_2) = \\{ 1, 2, \\ldots , n\_i \\} - D(X y\_1) \\cup D(X y\_2) \\\\ D(X y\_1 y\_2)&= \\{ 1, 2, \\ldots , n\_i \\} - L(X y\_1 y\_2) = D(X y\_1) \\cup D(X y\_2) \\end{aligned} \\end{aligned}

σ(Xy1y2)\=ni−|D(Xy1y2)|\\sigma (X y\_1 y\_2) = n\_i - |D(X y\_1 y\_2)|. If |D(Xy1y2)|\>ni2|D(X y\_1 y\_2)| > \\frac{n\_i}{2}, the tid-set of Xy1y2X y\_1 y\_2 is transformed into the tid-list format.

**_Case 3_**: _the intersection of bit-vector and bit-vector_.

Given two itemsets Xy1Xy\_1 and Xy2Xy\_2, bit-vector of Xy1Xy\_1 is BV(Xy1)BV(Xy\_1) and the bit-vector of Xy2Xy\_2 is BV(Xy2)BV(Xy\_2). The intersection of the tid-sets of Xy1Xy\_1 and Xy2Xy\_2 is: BV(Xy1y2)\=BV(Xy1)&BV(Xy2)BV(X y\_1 y\_2) = BV(X y\_1) \\& BV(X y\_2), where & is the bitwise AND operator. σ(Xy1y2)\\sigma (X y\_1 y\_2) is the number of bit 1 in BV(Xy1y2)BV(X y\_1 y\_2). If ⌈ni8⌉\>4×σ(Xy1y2)\\lceil \\frac{n\_i}{8} \\rceil > 4 \\times \\sigma (X y\_1 y\_2), BV(Xy1y2)BV(X y\_1 y\_2) is converted into the tid-list form.

_The number of bit 1 in bit-vector_. A simple way to compute the number of bit 1 in BV(Xy1y2)BV(X y\_1 y\_2) is checking whether the _a_th bit of BV(Xy1y2)BV(X y\_1 y\_2) is 1 (∀1≤a≤ni\\forall 1 \\le a \\le n\_i) and accumulating the counts. But, a better option is table-driven and counting the number of bit 1 in each byte directly. A hash table with 256 key-value pairs is utilized to map each byte value to the number of bit 1 in it, which can be pre-computed. Each byte value in the bit-vector can be retrieved sequentially and its number of bit 1 can be obtained directly by the hash table.

**_Case 4_**: _the intersection of tid-list and dif-list_.

Given two itemsets Xy1Xy\_1 and Xy2Xy\_2, tid-list of Xy1Xy\_1 is L(Xy1)L(Xy\_1) and the dif-list of Xy2Xy\_2 is D(Xy2)D(Xy\_2). The intersection of the tid-sets of Xy1Xy\_1 and Xy2Xy\_2 is:

L(Xy1y2)\=L(Xy1)∩L(Xy2)\=L(Xy1)∩({1,2,…,ni}−D(Xy2))\=L(Xy1)−L(Xy1)∩D(Xy2)\=L(Xy1)−D(Xy2)

\\begin{aligned} \\begin{aligned} L(X y\_1 y\_2)&= L(Xy\_1) \\cap L(Xy\_2) = L(X y\_1) \\cap (\\{ 1, 2, \\ldots , n\_i \\} - D(X y\_2)) \\\\&= L(X y\_1) - L(X y\_1) \\cap D(X y\_2) = L(X y\_1) - D(X y\_2) \\end{aligned} \\end{aligned}

The last equation can be proved in Theorem [5](/article/10.1007/s41019-024-00241-2#FPar24). The formula above is very intuitive. L(Xy1)L(X y\_1) keeps the tids of the transactions containing Xy1X y\_1 and D(Xy2)D(X y\_2) maintains the tids of the transactions not containing Xy2X y\_2. Of course, L(Xy1)−D(Xy2)L(X y\_1) - D(X y\_2) represents the tids of the transactions containing both Xy1Xy\_1 and Xy2Xy\_2, i.e., L(Xy1)∩L(Xy2)L(Xy\_1) \\cap L(Xy\_2). σ(Xy1y2)\=|L(Xy1y2)|\\sigma (X y\_1 y\_2 ) = |L(X y\_1 y\_2)|.

**_Case 5_**: _the intersection of tid-list and bit-vector_.

Given two itemsets Xy1Xy\_1 and Xy2Xy\_2, tid-list of Xy1Xy\_1 is L(Xy1)L(Xy\_1) and the bit-vector of Xy2Xy\_2 is BV(Xy2)BV(Xy\_2). The intersection of the tid-sets of Xy1X y\_1 and Xy2X y\_2 is kept as a tid-list L(Xy1y2)L(X y\_1 y\_2). ∀a∈L(Xy1)\\forall a \\in L(X y\_1), if the _a_th bit of BV(Xy2)BV(X y\_2) is 1, _a_ is inserted into L(Xy1y2)L(X y\_1 y\_2). σ(Xy1y2)\=|L(Xy1y2)|\\sigma (X y\_1 y\_2) = |L(X y\_1 y\_2)|.

**_Case 6_**: _the intersection of dif-list and bit-vector_.

Given two itemsets Xy1Xy\_1 and Xy2Xy\_2, dif-list of Xy1Xy\_1 is D(Xy1)D(Xy\_1) and the bit-vector of Xy2Xy\_2 is BV(Xy2)BV(Xy\_2). The intersection of the tid-sets of Xy1X y\_1 and Xy2X y\_2 is kept as a bit-vector BV(Xy1y2)BV(X y\_1 y\_2), which firstly is a copy of BV(Xy2)BV(X y\_2). ∀a∈D(Xy1)\\forall a \\in D(X y\_1), the _a_th transaction does not contain Xy1X y\_1, the _a_th bit of BV(Xy1y2)BV(X y\_1 y\_2) is set to 0. σ(Xy1y2)\\sigma (X y\_1 y\_2) is the number of bit 1 in BV(Xy1y2)BV(X y\_1 y\_2). If ⌈ni8⌉\>4×σ(Xy1y2)\\lceil \\frac{n\_i}{8} \\rceil > 4 \\times \\sigma (X y\_1 y\_2), BV(Xy1y2)BV(X y\_1 y\_2) is converted into the tid-list form.

### 5.4 Improvement 2: Candidate Pruning

For the root element Xrt\=Xy1X\_{rt} = X y\_1 removed from _QE_, if σ(Xy1)\>rmsup\\sigma (X y\_1) > rmsup, PTF expands it with the items in ARiAR\_i after y1y\_1. Let y1y\_1 be the _a_th item in ARiAR\_i. According to the basic implementation, ∀y2∈ARi(a+1,…,|ARi|)\\forall y\_2 \\in AR\_i(a + 1, \\ldots , |AR\_i|), if the itemset Xy2X y\_2 is kept in _HT_, PTF generates the itemsets Xy1y2X y\_1 y\_2 by intersecting the tid-sets of Xy1X y\_1 and Xy2X y\_2. However, the intersection of two tid-sets is relatively expensive, and we want to reduce the computation cost effectively.

In the initialization of _rmsup_, if a 1-itemset or 2-itemset belongs to top-_k_ frequent itemsets, it has been maintained in _MH_. Before processing PiP\_i, ARiAR\_i maintains the |ARi||AR\_i| items with the largest supports, satisfying the condition: ∀xj∈ARi−xi\\forall x\_j \\in AR\_i - x\_i, σ(xixj)\>rmsup\\sigma (x\_i x\_j) > rmsup.

_Timeliness pruning_. To merge Xy1X y\_1 and Xy2X y\_2, the former is the root element of _QE_, and the latter is found to be kept in _HT_. Of course, we have σ(Xy1)\>rmsup\\sigma (X y\_1) > rmsup currently. For Xy2X y\_2, it is kept in _HT_ because σ(Xy2)\\sigma (X y\_2) is greater than _rmsup_ of the time when Xy2X y\_2 is generated. Ever since Xy2X y\_2 is generated, the value of _rmsup_ could be increased and be no less than σ(Xy2)\\sigma (X y\_2) now. Therefore, before intersecting the tid-sets of Xy1X y\_1 and Xy2X y\_2, PTF first checks whether σ(Xy2)\\sigma (X y\_2) is greater than the current _rmsup_. If σ(Xy2)≤rmsup\\sigma (X y\_2) \\le rmsup, there is no need to merge Xy1X y\_1 and Xy2X y\_2.

**Fig. 13**

[![figure 13](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig13_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/13)

The illustration of hybrid search strategy. For some partition, there are five promising items x1,x2,x3,x4,x5x\_1, x\_2, x\_3, x\_4, x\_5. Suppose that x1x2x3x4x\_1 x\_2 x\_3 x\_4 is the next itemset to be explored

[Full size image](/article/10.1007/s41019-024-00241-2/figures/13)

_Last-item pruning_. For Xy2X y\_2 which is not pruned by timeliness pruning, we have σ(Xy2)\>rmsup\\sigma (X y\_2) > rmsup. If Xy1y2X y\_1 y\_2 is a top-_k_ frequent itemset, then all its subsets should belong to FIkFI\_k. Because σ(Xy1)\>rmsup\\sigma (X y\_1) > rmsup and σ(Xy2)\>rmsup\\sigma (X y\_2) > rmsup, the support of any subset of Xy1X y\_1 and Xy2X y\_2 is greater than _rmsup_ due to downward closure property. In another word, if the support of any itemset in P−(Xy1y2)−P(Xy1)−P(Xy2)\\mathcal {P}^-(X y\_1 y\_2) - \\mathcal {P}(X y\_1) - \\mathcal {P}(X y\_2), where P−(Xy1y2)\\mathcal {P}^-(X y\_1 y\_2) represents the powerset of Xy1y2X y\_1 y\_2 excluding empty set and Xy1y2Xy\_1y\_2 itself, is no greater than _rmsup_, we do not need to merge Xy1X y\_1 and Xy2X y\_2. However, due to the hybrid search strategy PTF adopts, the operation of checking all itemsets in P−(Xy1y2)−P(Xy1)−P(Xy2)\\mathcal {P}^-(X y\_1 y\_2) - \\mathcal {P}(X y\_1) - \\mathcal {P}(X y\_2) could go wrong, discarding the top-_k_ frequent itemsets incorrectly. As illustrated in Fig. [13](/article/10.1007/s41019-024-00241-2#Fig13), without loss of generality, let the promising items be x1,x2,x3,x4,x5x\_1, x\_2, x\_3, x\_4, x\_5 when processing partition P1P\_1, and the hybrid search strategy can be depicted by a growing tree. The root of the tree is x1x\_1 since all transactions begin with x1x\_1. According to the execution of PTF dealing with single partition, the 2-itemsets x1x2x\_1x\_2, x1x3x\_1x\_3, x1x4x\_1x\_4 and x1x5x\_1x\_5 are maintained in max heap _QE_ initially. This corresponds to one level extension for the tree. Let x1x2x\_1x\_2 be the root element of _QE_ then, which is removed from _QE_ and extended by the following promising items {x3,x4,x5}\\{ x\_3, x\_4, x\_5 \\}, and the subtree rooted at x2x\_2 extends one level with three leaves. We do not consider the pruning operation in this step temporarily, since x2x3x\_2x\_3, x2x4x\_2x\_4, x2x5x\_2x\_5 may be kept in _MH_ in the initialization of _rmsup_. Let x1x2x3x\_1x\_2x\_3 be the next root element of _QE_ to be selected and we want to expand it by x4x\_4, i.e., merging x1x2x3x\_1 x\_2 x\_3 and x1x2x4x\_1 x\_2 x\_4. Suppose now we perform the pruning by using of the constituent subsets. Because x1x3x4∈P−(x1x2x3x4)−P(x1x2x3)−P(x1x2x4)x\_1 x\_3 x\_4 \\in \\mathcal {P}^-(x\_1 x\_2 x\_3 x\_4) - \\mathcal {P}(x\_1 x\_2 x\_3) - \\mathcal {P}(x\_1 x\_2 x\_4) and x1x3x4x\_1 x\_3 x\_4 is not be generated yet, we may prune x1x2x3x4x\_1 x\_2 x\_3 x\_4 by mistake. Therefore, when merging Xy1X y\_1 and Xy2X y\_2, PTF only checks whether y1y2y\_1 y\_2 is contained in _MH_, the _k_ itemsets with the largest supports discovered so far. This is because, in the initialization of _rmsup_, any 2-itemset, if it belongs to FIkFI\_k, is kept in _MH_ already. If y1y2y\_1 y\_2 is not contained in _MH_, σ(y1y2)≤rmsup\\sigma (y\_1 y\_2) \\le rmsup, we do not need to merge Xy1X y\_1 and Xy2X y\_2.

### 5.5 Analysis

This part includes the theorems and their proofs used in this section.

### Theorem 2

Given a prefix-based partition PiP\_i, if |ARi|≤2|AR\_i| \\le 2, the processing of PiP\_i cannot generate any new top-_k_ frequent itemsets.

### Proof

All transactions in PiP\_i share the same prefix item xix\_i, the maximum support of the itemsets that can be generated in PiP\_i is no larger than that of {xi}\\{ x\_i \\}.

*   If |ARi|\=0|AR\_i| = 0, the support of {xi}\\{ x\_i \\} is no larger than _rmsup_, supports of any itemsets generated in PiP\_i are no larger than _rmsup_.
    
*   If |ARi|\=1|AR\_i| = 1 or 2, only 1-itemsets or 2-itemsets are needed to be checked in PiP\_i. Considering that in the initialization of _rmsup_, _MH_ has maintained the 1-itemsets and 2-itemsets that are possible to be top-_k_ frequent itemsets. PTF still does not need to deal with PiP\_i.
    

In short, if |ARi|≤2|AR\_i| \\le 2, the processing of PiP\_i cannot generate any new top-_k_ frequent itemsets. ◻\\square

### Theorem 3

When expanding the itemset Xy1X y\_1 with another item y2y\_2 where y1≺y2y\_1 \\prec y\_2, if HT(Xy2)HT(X y\_2) = null, σ(Xy2)≤rmsup\\sigma (X y\_2) \\le rmsup.

### Proof

First, note that ARiAR\_i maintains the promising items in PiP\_i. ∀xj∈ARi−xi\\forall x\_j \\in AR\_i - x\_i, the 2-itemset xixjx\_i x\_j and its tid-set are maintained in _HT_, and xixjx\_i x\_j is kept in _QE_.

Before the growth of the itemsets, all itemsets in _QE_ are 2-itemsets, and the first root element removed is 2-itemsets also. Let Xy1(X\=xi)X y\_1 (X = x\_i) be the current root element and y2y\_2 be the item satisfying y1≺y2y\_1 \\prec y\_2, if Xy2X y\_2 is not kept in _HT_, it means σ(Xy2)≤rmsup\\sigma (X y\_2) \\le rmsup because _HT_ maintains all the 2-itemsets with prefix item xix\_i whose supports are greater than _rmsup_. After the expansion for Xy1X y\_1, _HT_ and _QE_ maintains the 3-itemsets beginning with xiy1x\_i y\_1 whose supports are greater than _rmsup_.

During the execution, let the current root element be Xy1X y\_1, where |Xy1|≥3|X y\_1| \\ge 3. According to the growth strategy, Xy1X y\_1 is generated by expanding _X_ with y1y\_1 in the previous execution. In that process, not only y1y\_1, all the promising items in ARiAR\_i after the last item of _X_ are used to expand _X_ also. _HT_ and _QE_ only keep the expanded itemsets whose supports are greater than _rmsup_. Let y2y\_2 be the item to be expanded with Xy1X y\_1. If Xy2X y\_2 is not kept in _HT_, σ(Xy2)≤rmsup\\sigma (X y\_2) \\le rmsup. ◻\\square

### Theorem 4

If QE.max≤rmsupQE.max \\le rmsup, there is no need to process PiP\_i further and the processing of PiP\_i can terminate.

### Proof

According to the property of max heap, XrtX\_{rt} has the maximum support among the itemsets in _QE_. For any itemset X1X\_1 that is not generated so far, it is definitely the superset of some itemset X2X\_2 in _QE_ in terms of the growth strategy, and σ(X1)≤σ(X2)\\sigma (X\_1) \\le \\sigma (X\_2) due to the anti-monotone property. Obviously, σ(X1)≤σ(Xrt)\\sigma (X\_1) \\le \\sigma (X\_{rt}). Therefore, if QE.max≤rmsupQE.max \\le rmsup, it means that the supports of all the itemsets in _QE_ and the itemsets undiscovered so far are no greater than _rmsup_, they cannot be the top-_k_ frequent itemsets. The processing of PiP\_i can terminate. ◻\\square

### Theorem 5

Given L(Xy1)L(X y\_1) and D(Xy2)D(X y\_2), we have L(Xy1)−L(Xy1)∩D(Xy2)\=L(Xy1)−D(Xy2)L(X y\_1) - L(X y\_1) \\cap D(X y\_2) = L(X y\_1) - D(X y\_2).

### Proof

(1) ∀a∈L(Xy1)\\forall a \\in L(X y\_1) and a∈D(Xy2)a \\in D(X y\_2), a∈L(Xy1)∩D(Xy2)a \\in L(X y\_1) \\cap D(X y\_2), we have a∉L(Xy1)−L(Xy1)∩D(Xy2)a \\notin L(X y\_1) - L(X y\_1) \\cap D(X y\_2) and a∉L(Xy1)−D(Xy2)a \\notin L(X y\_1) - D(X y\_2). (2) ∀a∈L(Xy1)\\forall a \\in L(X y\_1) and a∉D(Xy2)a \\notin D(X y\_2), we have a∉L(Xy1)∩D(Xy2)a \\notin L(X y\_1) \\cap D(X y\_2), a∈L(Xy1)−L(Xy1)∩D(Xy2)a \\in L(X y\_1) - L(X y\_1) \\cap D(X y\_2) and a∈L(Xy1)−D(Xy2)a \\in L(X y\_1) - D(X y\_2). (3) ∀a∉L(Xy1)\\forall a \\notin L(X y\_1), no matter whether a∈D(Xy2)a \\in D(X y\_2) or not, a∉L(Xy1)−L(Xy1)∩D(Xy2)a \\notin L(X y\_1) - L(X y\_1) \\cap D(X y\_2) and a∉L(Xy1)−D(Xy2)a \\notin L(X y\_1) - D(X y\_2). All possibilities are included and the equation is satisfied. ◻\\square

## 6 Performance Evaluation

In this section, PTF is implemented in Java with jdk-15\_windows-x64 to evaluate its performance. The experiments are executed on DELL Precision T3431 Workstation (Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz (8 cores) + 32 G memory + 64bit windows 10).

The performance of PTF is evaluated against the latest top-_k_ FIM algorithms, FP-tree-based CRM \[[45](/article/10.1007/s41019-024-00241-2#ref-CR45 "Pyun G, Yun U (2014) Mining top-k frequent patterns with combination reducing techniques. Appl Intell 41(1):76–98")\] and level-wise-based MTK \[[15](/article/10.1007/s41019-024-00241-2#ref-CR15 "Chuang K-T, Huang J-L, Chen M-S (2008) Mining phtop-k frequent patterns in the presence of the memory constraint. VLDB J 17(5):1321–1344")\]. The performances of other algorithms \[[14](/article/10.1007/s41019-024-00241-2#ref-CR14 "Cheung Y-L, Fu AW-C (2004) Mining frequent itemsets without support threshold: With and without item constraints. IEEE Trans Knowl Data Eng 16(9):1052–1069")\] are reported to be inferior to the two algorithms. _In order to evaluate the performance better, the initialization of rmsup, which is proposed in PTF, is also adopted in CRM and MTK_. For CRM, a higher initial _rmsup_ makes a much smaller FP-tree and a better efficiency. For MTK, the initialization _saves the first scan_ in initial step, which reduces the I/O cost and computation cost. In the experiments, the performance is evaluated in synthetic data sets and real-life data sets. The used parameter settings are listed in Table [2](/article/10.1007/s41019-024-00241-2#Tab2). The parameter δ\\delta of MTK is set to 3 on synthetic data sets and to 2 on real-life data sets, the best choice of δ\\delta as stated in \[[15](/article/10.1007/s41019-024-00241-2#ref-CR15 "Chuang K-T, Huang J-L, Chen M-S (2008) Mining phtop-k frequent patterns in the presence of the memory constraint. VLDB J 17(5):1321–1344")\]. For the top-rank-_k_ FIM algorithm, we do not evaluate it in the experiments. The reason is that, (1) its definition is not exactly same as the top-_k_ FIM, and multiple itemsets can have the same rank, (2) its prefix-tree-based execution mode makes it hold the same performance issue as CRM, which will be illustrated in the experiments.

**Table 2 Parameter settings in experiments**

[Full size table](/article/10.1007/s41019-024-00241-2/tables/2)

**Table 3 The characteristic of the real-life data sets**

[Full size table](/article/10.1007/s41019-024-00241-2/tables/3)

_Synthetic data sets_. The synthetic data sets are generated by the data generator in \[[5](/article/10.1007/s41019-024-00241-2#ref-CR5 "Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of 20th international conference on very large data bases, pp 487–499")\], in which the number of maximal potential large itemsets is set to be double that of the number of items, and the average size of maximal potentially frequent itemset is set to 6. On synthetic data sets, the performance of PTF is evaluated in terms of four aspects: transaction number (_n_), result number (_k_), the number of total items (_d_) and the average transaction width (_m_).

_Real-life data sets_. The six real-life data sets, Chainstore, OnlineRetail, Accidents, Connect, Pumsb and Susy are selected from the SPMF data mining library \[[22](/article/10.1007/s41019-024-00241-2#ref-CR22 "Fournier-Viger, P, Lin JC-W, Gomariz A, Gueniche T et al (2016) The SPMF open-source data mining library version 2. In: Proceedings of 19th European conference on principles of data mining and knowledge discovery, Part III, volume 9853 of LNCS. Springer, Berlin, pp 36–40")\]. They hold different characteristics in several aspects and are used to evaluate the performance of PTF on real-life data more comprehensively. SPMF provides real-life data sets commonly used in the related research fields. Although the data sets available in SPMF are of small and medium size, they reflect the data characteristic in the real world. Table [3](/article/10.1007/s41019-024-00241-2#Tab3) shows the characteristics of the used real-life data sets, consisting of sparse type and dense type. The selected real-life data sets include the largest dense data set (Susy) and the largest sparse customer transaction data set (Chainstore) in SPMF. Some data sets of small size are also selected to compare PTF with the state-of-the-art algorithms, because the devised PTF focuses on massive data and its performance on small-size data sets is also intriguing.

**Table 4 The space comparison of hybrid vertical storage, direct form, CRM and MTK on real-life data sets, rhvs\=SIZEhybridverticalSIZEtransTabler\_{hvs} = \\frac{SIZE\_{hybridvertical}}{SIZE\_{transTable}} and rdrt\=SIZEdirectformSIZEtransTabler\_{drt} = \\frac{SIZE\_{directform}}{SIZE\_{transTable}}, rcrm|mtk\=SIZEtransTableSIZEtransTabler\_{crm|mtk} = \\frac{SIZE\_{transTable}}{SIZE\_{transTable}}, CRM and MTK are executed on the original transaction table, their space consumption is equal to the size of transaction table**

[Full size table](/article/10.1007/s41019-024-00241-2/tables/4)

_The space consumption of prefix-based partitioning_. The hybrid vertical storage selects the storage formats of the tid-sets of the items with the minimum sizes. On synthetic data sets, given m\=15m = 15, the prefix-based partitions in hybrid vertical storage mode incurs about 5 times larger space consumption than the original transaction table. Relatively, the prefix-based partitions in the direct form need about 9 times larger space consumption. On real-life data sets, the space consumption comparison is listed in Table [4](/article/10.1007/s41019-024-00241-2#Tab4). Normally, hybrid vertical storage can help reduce the space consumption effectively. On Chainstore data set, hybrid vertical storage mode generates a larger space consumption compared with the direct form, because this data set has many items and the tid-set of each item is stored in direct form with the extra data of 12 bytes. According to the characteristics of the available real data sets \[[22](/article/10.1007/s41019-024-00241-2#ref-CR22 "Fournier-Viger, P, Lin JC-W, Gomariz A, Gueniche T et al (2016) The SPMF open-source data mining library version 2. In: Proceedings of 19th European conference on principles of data mining and knowledge discovery, Part III, volume 9853 of LNCS. Springer, Berlin, pp 36–40")\], the number of the total items in the vast majority of cases is not too high, and the space consumption of hybrid vertical storage mode can stay within a reasonable range. For the cases that the number of items is much high and the average transaction width is relatively small, the overhead of extra 12 bytes for each tid-set is obviously significant, and the space consumption of hybrid vertical storage mode may be even larger than that of direct form. _Note that, the comparison results mentioned above actually include the space consumption of CRM and MTK_. Since the two algorithms process the original data directly, the space consumption is equal to the size of original transaction table. The comparison results of hybrid vertical storage and direct form with transaction table are just the comparison of space consumption of PTF, CRM and MTK. In this case, PTF can maintain only a small number of the most frequent items rather than all items in the prefix-based partitions. As verified in the experiments, only a small fraction of the items are promising items when PTF processes the partitions.

**Fig. 14**

[![figure 14](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig14_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/14)

The effect of transaction number

[Full size image](/article/10.1007/s41019-024-00241-2/figures/14)

### 6.1 The Effect of Transaction Number

Given k\=3000k = 3000, d\=1500d = 1500 and m\=15m = 15, experiment 1 evaluates the performance of PTF with varying transaction numbers. The execution times of PTF, MTK and CRM are shown in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14)a. Note that we only report the experimental results of CRM at n\=107n = 10^7 in the experiments of synthetic data sets, because the constructed FP-tree exceeds the memory limit at the larger values of _n_. As illustrated in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14)a, PTF runs 255.948 times faster than MTK averagely. The execution time of CRM (110.105 s) at n\=107n = 10^7 is very close to that of MTK (145.275 s). The speedup ratio of PTF over MTK increases with a greater value of _n_, from 41.842 at n\=107n = 10^7 to 477.172 at n\=100×107n = 100 \\times 10^7.

The significant performance advantage comes from the less I/O cost, the fewer candidates and the more efficient computation. As depicted in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14), PTF only involves 73.102 times less I/O cost than MTK. The I/O cost of CRM at n\=107n = 10^7 is equal to that of MTK. In experiment 1, MTK only needs to perform two full table scans, indicating that PTF only retrieves less than 136\\frac{1}{36} data of the original transaction table. The candidate numbers of PTF and MTK are reported in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14)c. The candidate number of MTK is the total number of candidates during its δ\\delta\-stair search, and the candidate number of PTF is the total number of itemsets explored actually in vertical mining. It is reported that PTF has 2.318 times fewer candidates than MTK.

The effect of hybrid vertical storage is illustrated in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14)d, which is compared with the size of the involved tid-sets in tid-list format. By hybrid vertical storage, the size of the retrieved data in PTF decreases by 10.739 times. The effect of candidate pruning is reported in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14)e. The pruning ratio is computed by the number of pruned candidates over the sum of the pruned candidates and the explored candidates actually before the termination condition is satisfied. The pruning ratio is not significant, because the supports of all itemsets in _QE_ initially are greater than _rmsup_. Each expanded itemset, only if its support exceeds _rmsup_, will be kept in _QE_ for the further expansion. The numbers of the promising items for the partitions are depicted in Fig. [14](/article/10.1007/s41019-024-00241-2#Fig14)f. For any partition, if the number of the promising items is no greater than 2, PTF skips the partition directly. Given d\=1500d = 1500, the overwhelming majority of the partitions are skipped, and the processing of the rest of the partitions only involves much small number (≤20\\le 20) of promising items in experiment 1. Comparatively, given the _rmsup_ value after initialization by _CoN_, a majority of the items are promising items (more than 1200 in experiment 1) when computing on the whole table.

**Fig. 15**

[![figure 15](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig15_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/15)

The effect of result number

[Full size image](/article/10.1007/s41019-024-00241-2/figures/15)

### 6.2 The Effect of Result Number

Given n\=10×107n = 10 \\times 10^7, d\=1500d = 1500 and m\=15m = 15, experiment 2 evaluates the performance of PTF with varying result numbers. A larger value of _k_ returns more frequent itemsets, and it leads to a smaller value of _rmsup_ naturally. The execution times of PTF and MTK should increase with a larger value of _k_. This also is reflected in Fig. [15](/article/10.1007/s41019-024-00241-2#Fig15)a, which shows that PTF runs 653.728 times faster than MTK. Relatively speaking, the rising trend of execution time of MTK is faster than that of PTF. At k\=10000k = 10000, the speedup ratio of PTF over MTK reaches to three orders of magnitude. For PTF, the quick increasing of execution time from k\=1000k = 1000 to k\=3000k = 3000 can be explained that, when k\=1000k = 1000, the initialized _rmsup_ by _CoN_ is very high that only 23 partitions are processed actually. The similar variation trends are also reflected in the I/O cost (Fig. [15](/article/10.1007/s41019-024-00241-2#Fig15)b) and the candidate number (Fig. [15](/article/10.1007/s41019-024-00241-2#Fig15)c). On average, PTF involves 122.331 times less I/O cost than MTK, which performs one full table scan at k\=1000k = 1000 and two full table scans at other values of _k_. PTF also maintains 2.319 fewer candidates than MTK. The effect of hybrid vertical storage is depicted in Fig. [15](/article/10.1007/s41019-024-00241-2#Fig15)d, which shows that PTF in hybrid vertical storage involves 10.96 times less I/O cost than PTF in the direct tid-list storage. The effect of candidate pruning is reported in Fig. [15](/article/10.1007/s41019-024-00241-2#Fig15)e. The numbers of the promising items for the partitions are illustrated in Fig. [15](/article/10.1007/s41019-024-00241-2#Fig15)f, indicating that more partitions can be skipped directly at a smaller value of _k_.

**Fig. 16**

[![figure 16](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig16_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/16)

The effect of item number

[Full size image](/article/10.1007/s41019-024-00241-2/figures/16)

### 6.3 The Effect of Item Number

Given n\=10×107n = 10 \\times 10^7, k\=3000k = 3000 and m\=15m = 15, experiment 3 evaluates the performance of PTF with varying item numbers. When the value of _d_ rises from 500 to 2500, a fixed average transaction width means the synthetic data set becomes increasingly sparse. Therefore, the execution time and the candidate number are considered to be smaller with a greater value of _d_, which are reflected in Fig. [16](/article/10.1007/s41019-024-00241-2#Fig16)a, c, respectively. In experiment 3, PTF runs 231.395 times faster than MTK and maintains 2.289 times fewer candidates than MTK.

With a greater value of _d_, the I/O cost of PTF keeps decreasing, as shown in Fig. [16](/article/10.1007/s41019-024-00241-2#Fig16)b. Comparatively, the I/O cost of MTK first decreases from d\=500d = 500 to d\=1000d = 1000, then remains unchanged in experiment 3. For PTF, the decline trend of I/O cost is due to the fewer promising items involved with a greater value of _d_, which is also depicted in Fig. [16](/article/10.1007/s41019-024-00241-2#Fig16)f. For MTK, except for d\=500d = 500, it needs to perform two full table scans.

PTF in the hybrid vertical storage reduces the retrieved data volume by 10.376 times compared with that in the direct tid-list format, as illustrated in Fig. [16](/article/10.1007/s41019-024-00241-2#Fig16)d. The effect of candidate pruning is reported in Fig. [16](/article/10.1007/s41019-024-00241-2#Fig16)e.

**Fig. 17**

[![figure 17](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig17_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/17)

The effect of transaction width

[Full size image](/article/10.1007/s41019-024-00241-2/figures/17)

### 6.4 The Effect of Average Transaction Width

Given n\=10×107n = 10 \\times 10^7, k\=3000k = 3000 and d\=1500d = 1500, experiment 4 evaluates the performance of PTF with varying average transaction widths. As illustrated in Fig. [17](/article/10.1007/s41019-024-00241-2#Fig17)a, with a greater value of _m_, the execution times of MTK and PTF both show the overall trend for increasing, and PTF runs 281.738 times faster than MTK. For one thing, the greater value of _m_ makes the transaction table of a larger size. For another, the cost of counting supports will be higher with the greater value of _m_. As depicted in Fig. [17](/article/10.1007/s41019-024-00241-2#Fig17)b, PTF involves 64.552 times less I/O cost than MTK. Although the candidate numbers of PTF and MTK exhibit obvious variation, we can still find a relatively steady trend in overall given the other unchanged parameters. As shown in Fig. [17](/article/10.1007/s41019-024-00241-2#Fig17)c, PTF maintains 2.606 times fewer candidates than MTK. As shown in Fig. [17](/article/10.1007/s41019-024-00241-2#Fig17)d, the hybrid vertical storage helps PTF reduces I/O cost by an order of magnitude. The effect of candidate pruning is depicted in Fig. [17](/article/10.1007/s41019-024-00241-2#Fig17)e. The numbers of the promising items are reported in Fig. [17](/article/10.1007/s41019-024-00241-2#Fig17)f. Although there are 1500 items, PTF only involves a much small number of promising items when processing the partitions.

**Fig. 18**

[![figure 18](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig18_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/18)

The first group of experiment 5 (Chainstore, sparse data)

[Full size image](/article/10.1007/s41019-024-00241-2/figures/18)

**Fig. 19**

[![figure 19](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig19_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/19)

The second group of experiment 5 (OnlineRetail, sparse data)

[Full size image](/article/10.1007/s41019-024-00241-2/figures/19)

**Fig. 20**

[![figure 20](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig20_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/20)

The third group of experiment 5 (Accidents, dense data)

[Full size image](/article/10.1007/s41019-024-00241-2/figures/20)

**Fig. 21**

[![figure 21](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig21_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/21)

The fourth group of experiment 5 (Connect, dense data)

[Full size image](/article/10.1007/s41019-024-00241-2/figures/21)

**Fig. 22**

[![figure 22](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig22_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/22)

The fifth group of experiment 5 (Pumsb, dense data)

[Full size image](/article/10.1007/s41019-024-00241-2/figures/22)

**Fig. 23**

[![figure 23](//media.springernature.com/lw685/springer-static/image/art%3A10.1007%2Fs41019-024-00241-2/MediaObjects/41019_2024_241_Fig23_HTML.png)](/article/10.1007/s41019-024-00241-2/figures/23)

The sixth group of experiment 5 (Susy, dense data)

[Full size image](/article/10.1007/s41019-024-00241-2/figures/23)

### 6.5 The Real-Life Data Sets

In experiment 5, the performance of PTF is evaluated on real-life data sets with varying result numbers. Since the used six real-life data sets are of small and medium size, the performance of FP-tree-based CRM is reported in experiment 5 also.

On the sparse data set, it normally has the relatively high number of items and short average transaction width. Therefore, MTK should perform well on sparse data sets of small and medium size, which is verified in Figs. [18](/article/10.1007/s41019-024-00241-2#Fig18)a and [19](/article/10.1007/s41019-024-00241-2#Fig19)a. MTK even is the best algorithm on Chainstore data when the result number is less than 10,000. CRM also makes good enough performance, and performs best on OnlineRetail data. The relatively small size of data does not liberate the full potential of PTF. For PTF, it has to retrieve the involved prefix-based partitions (349 partitions on chainstore data and 467 partitions on OnlineRetail data at k\=10000k = 10000 as shown in Figs. [18](/article/10.1007/s41019-024-00241-2#Fig18)d and [19](/article/10.1007/s41019-024-00241-2#Fig19)d), the time to locate the partitions can be amortized on massive data, but the effect is more significant on small and medium-sized data. However, the performance of PTF still is acceptable and can be comparable with the other two algorithms. As shown in Figs. [18](/article/10.1007/s41019-024-00241-2#Fig18)b and [19](/article/10.1007/s41019-024-00241-2#Fig19)b, PTF involves an order of magnitude less I/O cost than MTK and CRM. Since CRM needs two full table scans and MTK requires one or two full table scans, PTF only retrieves a small fraction of the table. As depicted in Figs. [18](/article/10.1007/s41019-024-00241-2#Fig18)c and [19](/article/10.1007/s41019-024-00241-2#Fig19)c, PTF maintains 4.177 times fewer candidates and 3.186 times fewer candidates than MTK on chainstore data and OnlineRetail data, respectively.

On the dense data set, it often has the relatively small number of items and long average transaction width. The performance of MTK is much poorer on dense data sets than that on sparse data sets. As shown in Figs. [20](/article/10.1007/s41019-024-00241-2#Fig20)a, [21](/article/10.1007/s41019-024-00241-2#Fig21)a, [22](/article/10.1007/s41019-024-00241-2#Fig22)a and [23](/article/10.1007/s41019-024-00241-2#Fig23)a, MTK is orders of magnitude slower than CRM and PTF, this can be explained that MTK has to maintain a large number of candidates as verified in Figs. [20](/article/10.1007/s41019-024-00241-2#Fig20)c, [21](/article/10.1007/s41019-024-00241-2#Fig21)c, [22](/article/10.1007/s41019-024-00241-2#Fig22)c and [23](/article/10.1007/s41019-024-00241-2#Fig23)c and the several full table scans for support counting. On Connect data and Pumsb data, CRM always shows the best performance, but the execution time of PTF is close to that of CRM. On Accidents data and Susy data, PTF even performs better than CRM in most cases. One overall advantage of PTF is that, it only involves a small fraction of table. As shown in Figs. [20](/article/10.1007/s41019-024-00241-2#Fig20)b, [21](/article/10.1007/s41019-024-00241-2#Fig21)b, [22](/article/10.1007/s41019-024-00241-2#Fig22)b and [23](/article/10.1007/s41019-024-00241-2#Fig23)b, the I/O cost of PTF is one order of magnitude less than that of the other algorithms. For one thing, much less data are retrieved, and for another, the computation cost for counting support is reduced correspondingly. The number of the processed partitions is depicted in Figs. [20](/article/10.1007/s41019-024-00241-2#Fig20)d, [21](/article/10.1007/s41019-024-00241-2#Fig21)d, [22](/article/10.1007/s41019-024-00241-2#Fig22)d and [23](/article/10.1007/s41019-024-00241-2#Fig23)d, a very small fraction of partitions have to be processed on dense data sets.

### 6.6 Discussion

Through the experimental evaluation demonstrated above, we can understand the performance advantage of PTF more comprehensively.

On massive data, all transactions cannot be maintained entirely in main memory. The performance advantage of PTF is much significant over the state-of-the-art algorithms. On massive data, FP-growth-based CRM algorithm even cannot initialize the required FP-tree. For MTK, its level-wise execution makes multiple-pass scan on the transaction table. On massive data, the I/O cost of MTK is very high. Comparatively, PTF utilizes the prefix-based partitioning, hybrid vertical storage mode and effective pruning strategies. It shows a much high efficiency on massive data. PTF can achieve up to three orders of magnitude speedup compared with MTK.

Although PTF focuses on dealing with massive data, we still evaluate its performance on six real-life data sets of small and medium size. For one thing, the performance of PTF should be evaluated against real-life data. For another, it is still expected to assess PTF more comprehensively. By and large, compared with state-of-the-art algorithms, PTF on data sets of small and medium size does not perform well as it is executed on massive data. For example, PTF, MTK and CRM have similar performance on sparse data sets of small and medium size. And on dense data set, although PTF performs much better than MTK, its execution time is very close to CRM. This can be elaborated from two aspects. Firstly, the prefix-partitioning, helping PTF acquire a high execution efficiency on massive data, affects the execution of PTF on data sets of small and medium size to some extent. The costs of locating the involve partitions can be neglected when deal with massive data, while the costs account for considerable proportion on data set of small and medium size, since the overall execution time is limited. Secondly, the proposed improvement strategies for PTF still remain valid here and the execution time of PTF always can be comparable against the best state-of-the-art algorithms.

According to the scope of massive data specified in Sect. [1.1](/article/10.1007/s41019-024-00241-2#Sec2), in the experiments, we do not consider the performance evaluation of parallel and distributed environment \[[37](/article/10.1007/s41019-024-00241-2#ref-CR37 "Li H, Wang Y, Zhang D, Zhang M, Chang EY (2008) PFP: parallel FP-growth for query recommendation. In: Pu P, Bridge DG, Mobasher B, Ricci F (eds) Proceedings of the 2008 ACM conference on recommender systems, RecSys 2008, Lausanne, Switzerland, October 23–25, 2008. ACM, pp 107–114")\]. It should be noted that a more efficient algorithm always is required to speed up the processing of mining problem on a larger scale of data. After all, we cannot _only rely on_ the computer cluster to deal with massive data, since the commonly scale-out approach has its limit due to technology and monetary wall \[[34](/article/10.1007/s41019-024-00241-2#ref-CR34 "Kersten ML, Sidirourgos L (2017) A database system with amnesia. In: 8th Biennial conference on innovative data systems research, CIDR 2017, Chaminade, CA, USA, January 8–11, 2017, Online Proceedings. 
http://www.cidrdb.org
")\]. In the experiments, we generate the synthetic data set of up to 10910^9 transactions to evaluate the performance of PTF. Besides, we select the real-life data sets from open-source SPMF data mining library, including two largest data sets of typical sparse and dense types for frequent itemset mining. As verified by the experimental results, the performance of PTF is evaluated in several aspects and PTF shows a satisfactory performance on massive data. In the future work, we will extend the idea of PTF algorithm to parallel and distributed environment.

In this part, we also discuss the issues of false negative and false positive for the results of PTF. A false negative is when a top-_k_ frequent itemset gets rejected, and a false positive is when an unqualified itemset is considered to be a top-_k_ frequent itemset. During the execution of PTF, apart from the candidate pruning strategy, PTF utilizes a min heap _MH_ to maintain the _k_ itemsets generated so far with the highest supports, computes the supports of the possible itemsets gradually, updates _MH_ if necessary. When the execution terminates, the itemsets in _MH_ naturally are the required results. Obviously, there is no false positive and no false negative now. With the candidate pruning strategy, the emphasis is whether PTF discards the top-_k_ frequent itemsets incorrectly. With timeliness pruning, PTF utilizes the actual supports of the itemsets used for extension to determine whether the pruning is performed. It does not discard the top-_k_ frequent itemsets. For last-item pruning, it uses the 2-itemsets formed by two last items to determine whether the pruning is executed. According to the anti-monotone property, it also does not discard the top-_k_ frequent itemsets. In short, there are no any false negatives or any false positives in the results of PTF.

## 7 Conclusion

This paper considers the problem of top-_k_ frequent itemset mining (top-_k_ FIM) on massive data. It is analyzed that the existing algorithms focus on the data set of small and medium size. On massive data, they either need several full table scans or have to construct the assistant structure which cannot be kept completely in the memory, incurring high execution cost. This paper develops a novel PTF algorithm, which is based on prefix-partitioning strategy, to mine top-_k_ frequent itemsets on massive data efficiently. The transactions in each prefix-based partition share the same prefix item and frequent itemsets with the prefix item can be computed in the partition separately. PTF processes the partitions sequentially, and the overwhelming majority of partitions, which cannot generate any top-_k_ frequent itemsets, can be skipped directly. For each partition to be processed, vertical mining is performed on the vertical representation of the promising items only by high-support-first principle. The hybrid vertical storage mode is devised to maintain the tid-sets of the items adaptively and reduce the execution cost significantly. The candidate pruning operations, including timeliness pruning and last-item pruning, are presented to reduce the number of the candidates. The extensive experimental results show that, compared with the existing algorithms, PTF can achieve up to three orders of magnitude speedup ratio.
"""