An Algorithm to Create Sorted FP-Growth Tree for Extracting Association Rules

An Algorithm to Create Sorted FP-Growth Tree for Extracting Association Rules | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article An Algorithm to Create Sorted FP-Growth Tree for Extracting Association Rules M. Barkhan, R. Ramazani, A. Kabani This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-2076910/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Mining data in massive databases to find useful data, frequent patterns (FP) and knowledge discovery, has been studied popularly in data mining research fields minding governments, industries and sales companies. In data mining, frequent patterns as growth tree are an efficient method for discovering knowledge and compressing information in a tree structure. Previous studies presented various methods to achieve frequent patterns which even require complex process and costs, particularly if the patterns overnumbered. In this paper we provide a divide and conquer algorithm based on FP-Growth Tree to create an initially sorted tree structure of the nodes that the most frequent patterns would be available at every moment of the tree construction procedure. In addition, we can consider a parameter to avoid inserting less frequent branches, thus, the tree would be sorted from the beginning of its formation. data mining big data FP-Growth Tree association rules Figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 1. introduction Association rules mining (ARM) has been noticed in the data mining research field significantly. ARM necessarily would be functional in various applications, such as cross-marketing, market basket analysis, fraud detection, filtering and etc. FP-Tree is an efficient and scalable algorithm to calculate frequent patterns that involved by ARM. This method concludes a prefix structure to compress and present FPs. Han et al. proved [1] that FP-Growth Tree method performs better than previous ones such as Apriori [2] or Treeprojection [3]. In other researches [4][5][6] FP-Growth was proved that even runs more efficient than Eclat [7] and Relim [8]. The FP-Growth performance reckoned to be more popular and many investigated to be optimized. FP-Growth algorithm is a suitable mining FPs solution without candidate generation, that utilize divide-and-conquer to gain association rules. Generally, this algorithm operates as the database would be compressed to present FPs as FP-Tree structure. 2. Related Works Zaki [9] has developed the equivalence class transformation (ECLAT) algorithm for frequent itemset mining. It relies on the intersection property and can perform both sequential and parallel computing. Unlike Apriori and FP-growth, ECLAT works vertically and creates a TID list for each item. Hyper-structure mining of frequent patterns (H-Mine) algorithm [10] proposed by Pei J et al. to overcome the FP-growth performance bottlenecks by using queues rather than a tree data structure. H-Mine organizes transaction items into distinct queues and uses hyperlinks to connect transactions having the same first item name. It is considered good for sparse datasets and is efficient in terms of memory and runtime consumption than Apriori and FP-growth. Li H et al. [11] introduced a parallel-processing-based algorithm which utilized three Map-Reduce phase to extract tasks of the FP-Growth and incorporate intermediate data. Grahne G. and Zhu J [12] have introduced a novel array-based technique that allows using FP-trees more efficiently when mining frequent itemsets. That technique greatly reduces the time spent traversing FP-trees, and works especially well for sparse datasets. Furthermore, the algorithms for mining maximal and closed frequent itemsets. The FP-growth* algorithm, which extends original FP-growth method, also uses the novel array technique to mine all frequent itemsets. They also proposed another FP-array approach [13] to minimize tree traversing time, but the recurring construction of conditional FP-trees still exists. Shawkat et al. [14] presented a new scheme to discover associations from a wide range of relations across the dataset. Trough combining the FP-tree* mining method and header table of FP-growth they developed an algorithm as MFP-growth. 3. Proposed Algorithm An Algorithm proposed which is called Sorted Frequent Pattern Growth Tree (SFP-Growth Tree) based on the basic FP-Tree theory designed to challenge a couple of issues. Firstly, in the basic FP-Tree, after the completion of operation, the resulted tree would have not been sorted and finding most frequent patterns requires the tree being sorted or spend the cost of search every time which would not be advantageous. To solve this challenge proposed algorithm creates a tree sorted from the initial levels to the end nodes. Secondly, users may do not want less-frequented patterns while all the transactions have to be inserted in the basic FP-Growth Tree. Due to being initially sorted tree by the proposed algorithm, the undesirable less-frequented patterns could be omitted and the result contain a pruned tree with the most frequented patterns according to the user’s setting. In this method, a node with its metadata is inserted in the tree once and it does not need to be updated until the end of operation. Achieving this aim, reading transactions must be reformed so that the tree grows level by level horizontally. Thus, instead of traversing the tree unregularly inserting nodes, level a must be filled then level a+1 be processed. The figure 1 illustrates nodes inserting sequence direction. In Table.1 , a transaction database is considered as an example that the data would be as the Frequent Items after the first scan[1] (preparation stage, sorting and applying min_support). Table 1 a transaction database as running example TID Items in Transaction (ordered) Frequent Items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o, f, c, a, b, m 300 b, f, h, j, o f, b 400 b, c, k, s, p c, b, p 500 a, f, c, e, l, p, m, n f, c, a, m, p Now, by the proposed algorithm the data should be read according to frequency. As the first entity of transactions are the most frequented item in that transaction construct level 1 of the tree. Then n th entity of each transaction constructs level n . In the example, the data f, c with the frequency of 4, 1 would be positioned at level 1. It is proposed that in each step of inserting nodes, insert them sorted. Next step, the transaction with f prefix would be read, the frequency of each node calculated and finally all the children created below the parent node at once sorted. The previous operation repeats for every node on the same level. This process repeats for every prefix of the tree until whole tree will be constructed sorted. The result SFP-Growth tree for the example would be as figure 4. Comparing the resulted tree to the tree of basic algorithm, the branches, paths and patterns are similar, however, the SFP-Growth Tree is sorted. 4. The advantageous of Sorted FP-Growth Tree In very large databases, aborting the process anytime, the top-most sorted nodes have been inserted in the tree to the aborting moment. During the tree construction process, each node is inserted once and no need to be updated. The node just will be read to find its children. Considering the theory of SFP-Growth Tree construction stages, we can apply a parameter which defines the importance of frequent patterns, such that at most how many children for each node are accepted that introduce the n most frequent paths would be saved. Moreover, the algorithm avoids to calculate the paths over the defined value, so, the resource consuming of operating will have been scrounged. Due to inserting the nodes into the tree sorted, there will no need to rebuild or sort the resulted tree. In previous example, if we consider the most-frequent parameter as 2 the resulted tree would be: 5. Conclusion Threshold of min_support is a suitable criterion to mine frequent patterns but not enough. Because it only considers a single item’s frequency. In Addition, utilizing other criterions such as min_conf would be complex and costly. In large databases, on the other hand, after mining patterns we find more of them useless. The proposed method can be useful to disregard those useless patterns. Moreover, a sorted large data in a compressed structure, can facilitate the next processes. Declarations Ethical Approval We further confirm that any aspect of the work covered in this manuscript that has involved human patients has been conducted with the ethical approval of all relevant bodies and that such approvals are acknowledged within the manuscript. Competing interests The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. We wish to draw the attention of the Editor to the following facts which may be considered as potential conflicts of interest and to significant financial contributions to this work. Authors' contributions We confirm that the manuscript has been read and approved by all named authors and that there are no other persons who satisfied the criteria for authorship but are not listed. We further confirm that the order of authors listed in the manuscript has been approved by all of us. Funding No funding was received for this work. Availability of data and materials We confirm that no special dataset was used in this paper. Intellectual Property We confirm that we have given due consideration to the protection of intellectual property associated with this work and that there are no impediments to publication, including the timing of publication, with respect to intellectual property. In so doing we confirm that we have followed the regulations of our institutions concerning intellectual property. We understand that the Corresponding Author is the sole contact for the Editorial process (including Editorial Manager and direct communications with the office). He is responsible for communicating with the other authors about progress, submissions of revisions and final approval of proofs. We confirm that we have provided a current, correct email address which is accessible by the Corresponding Author. References J. Han, H. Pei, and Y. Yin. Mining Frequent Patterns without Candidate Generation. In: Proc. Conf. on the Management of Data (SIGMOD’00, Dallas, TX). ACM Press, New York, NY, USA 2000 Agrawal, R. and Srikant, R. 1994. Fast algorithms for mining association rules. In Proc. 1994 Int. Conf. Very Large Data Bases (VLDB’94), Santiago, Chile, pp. 487–499. Agarwal, R., Aggarwal, C., and Prasad, V.V.V. 2001. A tree projection algorithm for generation of frequent itemsets. Journal of Parallel and Distributed Computing, 61:350–371. B.Santhosh Kumar and K.V.Rukmani. Implementation of Web Usage Mining Using APRIORI and FP Growth Algorithms. Int. J. of Advanced Networking and Applications, Volume: 01, Issue:06, Pages: 400-404 (2010). Cornelia Gyorödi and Robert Gyorödi. A Comparative Study of Association Rules Mining Algorithms. SACI 2004, 1st Romanian-Hungarian Joint Symposium on Applied Computational Intelligence. F. Bonchi and B. Goethals. FP-Bonsai: The Art of Growing and Pruning Small FP-trees. Proc. 8th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’04, Sydney, Australia), 155–160. Springer-Verlag, Heidelberg, Germany 2004. M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New Algorithms for Fast Discovery of Association Rules. Proc. 3rd Int. Conf. on Knowledge Discovery and Data Mining (KDD’97), 283–296. AAAI Press, Menlo Park, CA, USA 1997. Christian Borgelt. Keeping Things Simple: Finding Frequent Item Sets by Recursive Elimination. Workshop Open Source Data Mining Software (OSDM'05, Chicago, IL), 66-70. ACM Press, New York, NY, USA 2005 Zaki MJ (1997) Fast mining of sequential patterns in very large databases. University of Rochester Computer Science Department, New York 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 Data Mining. In: Proc.s IEEE Inter. Conf., IEEE, pp. 441–448 Li H, Wang Y, Zhang D, Zhang M, Chang EY (2009) PFP: parallel FP-growth for query recommendation. In: ACM Conference on Recommender Systems, pp. 107–114 Grahne G. and Zhu J. Efficiently Using Prefix-trees in Mining Frequent Itemsets, In Proc. of the IEEE ICDM Workshop on Frequent Itemset Mining, 2004 Grahne G, Zhu J (2005) Fast algorithms for frequent itemset mining using FP-trees. IEEE Trans Knowl Data Eng 17(10):1347–1362. https://doi.org/10.1109/TKDE.2005.166 Shawkat, M., Badawi, M., El-ghamrawy, S. et al. An optimized FP-growth algorithm for discovery of association rules. J Supercomput 78, 5479–5506 (2022). https://doi.org/10.1007/s11227-021-04066-y Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-2076910","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":138008717,"identity":"d2eb3b86-88a6-4648-bb63-040fd2ef3494","order_by":0,"name":"M. Barkhan","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAzElEQVRIiWNgGAWjYFACHiA+cICBgb2BgZlELTwHSNYikUCkFt0G3oOfK87ckTeXfGP4uaDChoG/vTsBrxazA3zJkmduPDPcOTvHWHrGmTQGiTNnNxDQwmMg2fDhMOOG2zkG0rxthxkMJHIJajH+CdRiv+HmGePfxGoxk2y4cThxww0eM2Jt4UuzbDhzOHnDmbQya54zaTxE+IX38M2GY4dtNxw/vPk2T4WNHH97L34tDPIPYCwOAxDJg185KmB/QEDBKBgFo2AUjFQAAFrsTkHyo2WTAAAAAElFTkSuQmCC","orcid":"","institution":"Mahabad Petrochemical Company","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"M.","middleName":"","lastName":"Barkhan","suffix":""},{"id":138008719,"identity":"c1bd3fb9-f6c8-4c63-8e6b-fdd3787e5b50","order_by":1,"name":"R. Ramazani","email":"","orcid":"","institution":"University of Applied Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"R.","middleName":"","lastName":"Ramazani","suffix":""},{"id":138008720,"identity":"c610b45e-f49e-4ccd-b1f7-69c484b592b0","order_by":2,"name":"A. Kabani","email":"","orcid":"","institution":"University of Applied Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"A.","middleName":"","lastName":"Kabani","suffix":""}],"badges":[],"createdAt":"2022-09-18 05:44:17","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-2076910/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-2076910/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":26845983,"identity":"b830cecb-36cc-4b3a-af62-1d412ea85168","added_by":"auto","created_at":"2022-09-22 20:37:25","extension":"png","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":23797,"visible":true,"origin":"","legend":"\u003cp\u003eInserting nodes direction\u003c/p\u003e","description":"","filename":"floatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-2076910/v1/c2ad999f245cffe68553bfe3.png"},{"id":26845985,"identity":"4939cf70-6523-42db-b0c2-c1a624fde2ba","added_by":"auto","created_at":"2022-09-22 20:37:26","extension":"png","order_by":2,"title":"Figure 2","display":"","copyAsset":false,"role":"figure","size":29948,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cem\u003ePositioning of level1 nodes\u003c/em\u003e\u003c/p\u003e","description":"","filename":"floatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-2076910/v1/e16e4cefce83e318da5efa24.png"},{"id":26845982,"identity":"13cb7f83-bc84-41f0-9674-a4c493b17300","added_by":"auto","created_at":"2022-09-22 20:37:25","extension":"png","order_by":3,"title":"Figure 3","display":"","copyAsset":false,"role":"figure","size":14842,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cem\u003ePositioning of level2 nodes\u003c/em\u003e\u003c/p\u003e","description":"","filename":"floatimage3.png","url":"https://assets-eu.researchsquare.com/files/rs-2076910/v1/cdfa857d426086f20729b133.png"},{"id":26845986,"identity":"9c18f283-fea7-414f-93eb-d91b633c28a1","added_by":"auto","created_at":"2022-09-22 20:37:26","extension":"png","order_by":4,"title":"Figure 4","display":"","copyAsset":false,"role":"figure","size":19545,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cem\u003eresulted tree\u003c/em\u003e\u003c/p\u003e","description":"","filename":"floatimage4.png","url":"https://assets-eu.researchsquare.com/files/rs-2076910/v1/1eb50b1fcb515590a5eb0172.png"},{"id":26845984,"identity":"e41fa383-a2d8-489a-9f7e-7e5aa8f6676c","added_by":"auto","created_at":"2022-09-22 20:37:25","extension":"png","order_by":5,"title":"Figure 5","display":"","copyAsset":false,"role":"figure","size":14591,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cem\u003ePruned Tree\u003c/em\u003e\u003c/p\u003e","description":"","filename":"floatimage5.png","url":"https://assets-eu.researchsquare.com/files/rs-2076910/v1/2dd1bb09fb2f412c3d9fe5c7.png"},{"id":27115516,"identity":"c30b37fe-f7a1-4300-be18-5a7606596241","added_by":"auto","created_at":"2022-09-29 02:59:26","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":274269,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-2076910/v1/3876fa4f-fdea-4a60-b56a-5929a2c22127.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"An Algorithm to Create Sorted FP-Growth Tree for Extracting Association Rules","fulltext":[{"header":"1. introduction","content":"\u003cp\u003eAssociation rules mining (ARM) has been noticed in the data mining research field significantly. ARM necessarily would be functional in various applications, such as cross-marketing, market basket analysis, fraud detection, filtering and etc. FP-Tree is an efficient and scalable algorithm to calculate frequent patterns that involved by ARM. This method concludes a prefix structure to compress and present FPs. Han et al. proved [1] that FP-Growth Tree method performs better than previous ones such as Apriori [2] or Treeprojection [3]. In other researches [4][5][6] FP-Growth was proved that even runs more efficient than Eclat [7] and Relim [8]. The FP-Growth performance reckoned to be more popular and many investigated to be optimized. FP-Growth algorithm is a suitable mining FPs solution without candidate generation, that utilize divide-and-conquer to gain association rules. Generally, this algorithm operates as the database would be compressed to present FPs as FP-Tree structure.\u0026nbsp;\u003c/p\u003e"},{"header":"2. Related Works","content":"\u003cp\u003eZaki [9] has developed the equivalence class transformation (ECLAT) algorithm for frequent itemset mining. It relies on the intersection property and can perform both sequential and parallel computing. Unlike Apriori and FP-growth, ECLAT works vertically and creates a TID list for each item.\u003c/p\u003e\n\u003cp\u003eHyper-structure mining of frequent patterns (H-Mine) algorithm [10] proposed by Pei J et al. to overcome the FP-growth performance bottlenecks by using queues rather than a tree data structure. H-Mine organizes transaction items into distinct queues and uses hyperlinks to connect transactions having the same first item name. It is considered good for sparse datasets and is efficient in terms of memory and runtime consumption than Apriori and FP-growth.\u003c/p\u003e\n\u003cp\u003eLi H et al. [11] introduced a parallel-processing-based algorithm which utilized three Map-Reduce phase to extract tasks of the FP-Growth and\u0026nbsp;incorporate intermediate data.\u003c/p\u003e\n\u003cp\u003eGrahne G. and Zhu J [12]\u0026nbsp;have introduced a novel array-based technique that allows using FP-trees more efficiently when mining frequent itemsets. That technique greatly reduces the time spent traversing FP-trees, and works especially well for sparse datasets. Furthermore, the algorithms for mining maximal and closed frequent itemsets. The FP-growth* algorithm, which extends original FP-growth method, also uses the novel array technique to mine all frequent itemsets. They also proposed another FP-array approach [13] to minimize tree traversing time, but the recurring construction of conditional FP-trees still exists.\u003c/p\u003e\n\u003cp\u003eShawkat et al. [14] presented a new scheme to discover associations from a wide range of relations across the dataset. Trough combining the FP-tree* mining method and header table of FP-growth they developed an algorithm as MFP-growth.\u003c/p\u003e"},{"header":"3. Proposed Algorithm","content":"\u003cp\u003eAn Algorithm proposed which is called Sorted Frequent Pattern Growth Tree (SFP-Growth Tree) based on the basic FP-Tree theory designed to challenge a couple of issues. Firstly, in the basic FP-Tree, after the completion of operation, the resulted tree would have not been sorted and finding most frequent patterns requires the tree being sorted or spend the cost of search every time which would not be advantageous. To solve this challenge proposed\u0026nbsp;algorithm creates a tree sorted from the initial levels to the end nodes. Secondly, users may do not want less-frequented patterns while all the transactions have to be inserted in the basic FP-Growth Tree. Due to being initially sorted tree by the proposed algorithm, the undesirable\u003cspan dir=\"RTL\"\u003e\u0026nbsp;\u003c/span\u003eless-frequented patterns could be omitted and the result contain a pruned tree with the most frequented patterns according to the user\u0026rsquo;s setting. In this method, a node with its metadata is inserted in the tree once and it does not need to be updated until the end of operation. Achieving this aim, reading transactions must be reformed so that the tree grows level by level horizontally. Thus, instead of traversing the tree unregularly inserting nodes, level \u003cem\u003ea\u0026nbsp;\u003c/em\u003emust be filled then level \u003cem\u003ea+1\u0026nbsp;\u003c/em\u003ebe processed. The figure 1 illustrates nodes inserting sequence direction.\u003c/p\u003e\n\u003cp\u003eIn \u003cem\u003eTable.1\u003c/em\u003e, a transaction database is considered as an example that the data would be as the \u003cem\u003eFrequent Items\u003c/em\u003e after the first scan[1] (preparation stage, sorting and applying min_support).\u003c/p\u003e\n\u003cp style=\"text-align: center;\"\u003e\u003cstrong\u003eTable 1\u003c/strong\u003e\u003c/p\u003e\n\u003cp style=\"text-align: center;\"\u003ea transaction database as running example\u003c/p\u003e\n\u003ctable border=\"1\" cellpadding=\"0\" cellspacing=\"0\" style=\"border-collapse: collapse; margin: 0px auto;\"\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd valign=\"top\" width=\"18.13804173354735%\"\u003e\n \u003cp\u003e\u003cstrong\u003eTID\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003e\u003cstrong\u003eItems in Transaction\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003e\u003cstrong\u003e(ordered) Frequent Items\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd valign=\"top\" width=\"18.13804173354735%\"\u003e\n \u003cp\u003e\u003cstrong\u003e100\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ef, a, c, d, g, i, m, p\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ef, c, a, m, p\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd valign=\"top\" width=\"18.13804173354735%\"\u003e\n \u003cp\u003e\u003cstrong\u003e200\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ea, b, c, f, l, m, o,\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ef, c, a, b, m\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd valign=\"top\" width=\"18.13804173354735%\"\u003e\n \u003cp\u003e\u003cstrong\u003e300\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003eb, f, h, j, o\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ef, b\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd valign=\"top\" width=\"18.13804173354735%\"\u003e\n \u003cp\u003e\u003cstrong\u003e400\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003eb, c, k, s, p\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ec, b, p\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd valign=\"top\" width=\"18.13804173354735%\"\u003e\n \u003cp\u003e\u003cstrong\u003e500\u003c/strong\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ea, f, c, e, l, p, m, n\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd valign=\"top\" width=\"40.93097913322632%\"\u003e\n \u003cp\u003ef, c, a, m, p\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003eNow, by the proposed algorithm the data should be read according to frequency. As the first entity of transactions are the most frequented item in that transaction construct level 1 of the tree. Then \u003cem\u003en\u003csup\u003eth\u003c/sup\u003e\u003c/em\u003e\u003csup\u003e\u003cspan dir=\"RTL\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/sup\u003e entity of each transaction constructs level \u003cem\u003en\u003c/em\u003e. In the example, the data \u003cem\u003ef, c\u003c/em\u003e\u003cspan dir=\"RTL\"\u003e\u0026nbsp;\u003c/span\u003ewith the frequency of \u003cem\u003e4, 1\u003c/em\u003e would be positioned at level 1.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eIt is proposed that in each step of inserting nodes, insert them sorted. Next step, the transaction with \u003cem\u003ef\u003c/em\u003e prefix would be read, the frequency of each node calculated and finally all the children created below the parent node at once sorted.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eThe previous operation repeats for every node on the same level.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eThis process repeats for every prefix of the tree until whole tree will be constructed sorted. The result SFP-Growth tree for the example would be as figure 4.\u003c/p\u003e\n\u003cp\u003eComparing the resulted tree to the tree of basic algorithm, the branches, paths and patterns are similar, however, the SFP-Growth Tree is sorted.\u003c/p\u003e"},{"header":"4. The advantageous of Sorted FP-Growth Tree","content":"\u003cul\u003e\n \u003cli\u003eIn very large databases, aborting the process anytime, the top-most sorted nodes have been inserted in the tree to the aborting moment.\u003c/li\u003e\n \u003cli\u003eDuring the tree construction process, each node is inserted once and no need to be updated. The node just will be read to find its children.\u003c/li\u003e\n \u003cli\u003eConsidering the theory of SFP-Growth Tree construction stages, we can apply a parameter which defines the importance of frequent patterns, such that at most \u003cem\u003ehow many\u0026nbsp;\u003c/em\u003echildren for each node are accepted that introduce the \u003cem\u003en\u0026nbsp;\u003c/em\u003emost frequent paths would be saved. Moreover, the algorithm avoids to calculate the paths over the defined value, so, the resource consuming of operating will have been scrounged.\u0026nbsp;\u003c/li\u003e\n \u003cli\u003eDue to inserting the nodes into the tree sorted, there will no need to rebuild or sort the resulted tree.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eIn previous example, if we consider the \u003cem\u003emost-frequent\u003c/em\u003e parameter as 2 the resulted tree would be:\u003c/p\u003e"},{"header":"5. Conclusion ","content":"\u003cp\u003eThreshold of min_support is a suitable criterion to mine frequent patterns but not enough. Because it only considers a single item\u0026rsquo;s frequency. In Addition, utilizing other criterions such as min_conf would be complex and costly. In large databases, on the other hand, after mining patterns we find more of them useless. The proposed method can be useful to disregard those useless patterns. Moreover, a sorted large data in a compressed structure, can facilitate the next processes.\u003c/p\u003e"},{"header":"Declarations","content":"\u003cp\u003e\u003cstrong\u003eEthical Approval\u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eWe further confirm that any aspect of the work covered in this manuscript that has involved human patients has been conducted with the ethical approval of all relevant bodies and that such approvals are acknowledged within the manuscript.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eCompeting interests\u003c/strong\u003e\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eThe authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. We wish to draw the attention of the Editor to the following facts which may be considered as potential conflicts of interest and to significant financial contributions to this work.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eAuthors\u0026apos; contributions\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eWe confirm that the manuscript has been read and approved by all named authors and that there are no other persons who satisfied the criteria for authorship but are not listed. We further confirm that the order of authors listed in the manuscript has been approved by all of us.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eFunding\u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eNo funding was received for this work.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eAvailability of data and materials\u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eWe confirm that no special dataset was used in this paper.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eIntellectual Property\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eWe confirm that we have given due consideration to the protection of intellectual property associated with this work and that there are no impediments to publication, including the timing of publication, with respect to intellectual property. In so doing we confirm that we have followed the regulations of our institutions concerning intellectual property.\u003c/p\u003e\n\u003cp\u003eWe understand that the Corresponding Author is the sole contact for the Editorial process (including Editorial Manager and direct communications with the office). He is responsible for communicating with the other authors about progress, submissions of revisions and final approval of proofs. We confirm that we have provided a current, correct email address which is accessible by the Corresponding Author.\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\n\u003cli\u003eJ. Han, H. Pei, and Y. Yin. Mining Frequent Patterns without Candidate Generation. In: Proc. Conf. on the Management of Data (SIGMOD\u0026rsquo;00, Dallas, TX). ACM Press, New York, NY, USA 2000 \u003c/li\u003e\n\u003cli\u003e Agrawal, R. and Srikant, R. 1994. Fast algorithms for mining association rules. In Proc. 1994 Int. Conf. Very Large Data Bases (VLDB\u0026rsquo;94), Santiago, Chile, pp. 487\u0026ndash;499. \u003c/li\u003e\n\u003cli\u003eAgarwal, R., Aggarwal, C., and Prasad, V.V.V. 2001. A tree projection algorithm for generation of frequent itemsets. Journal of Parallel and Distributed Computing, 61:350\u0026ndash;371.\u003c/li\u003e\n\u003cli\u003eB.Santhosh Kumar and K.V.Rukmani. Implementation of Web Usage Mining Using APRIORI and FP Growth Algorithms. Int. J. of Advanced Networking and Applications, Volume: 01, Issue:06, Pages: 400-404 (2010). \u003c/li\u003e\n\u003cli\u003eCornelia Gyor\u0026ouml;di and Robert Gyor\u0026ouml;di. A Comparative Study of Association Rules Mining Algorithms. SACI 2004, 1st Romanian-Hungarian Joint Symposium on Applied Computational Intelligence. \u003c/li\u003e\n\u003cli\u003eF. Bonchi and B. Goethals. FP-Bonsai: The Art of Growing and Pruning Small FP-trees. Proc. 8th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD\u0026rsquo;04, Sydney, Australia), 155\u0026ndash;160. Springer-Verlag, Heidelberg, Germany 2004. \u003c/li\u003e\n\u003cli\u003eM. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New Algorithms for Fast Discovery of Association Rules. Proc. 3rd Int. Conf. on Knowledge Discovery and Data Mining (KDD\u0026rsquo;97), 283\u0026ndash;296. AAAI Press, Menlo Park, CA, USA 1997. \u003c/li\u003e\n\u003cli\u003e Christian Borgelt. Keeping Things Simple: Finding Frequent Item Sets by Recursive Elimination. Workshop Open\u003cspan dir=\"RTL\"\u003e \u003c/span\u003eSource Data Mining Software (OSDM\u0026apos;05, Chicago, IL), 66-70. ACM Press, New York, NY, USA 2005 \u003c/li\u003e\n\u003cli\u003eZaki MJ (1997) Fast mining of sequential patterns in very large databases. University of Rochester Computer Science Department, New York\u003c/li\u003e\n\u003cli\u003ePei J, Han J, Lu H, Nishio S, Tang S, Yang D (2001) H-mine: hyper-structure mining of frequent patterns in large databases. In Data Mining. In: Proc.s IEEE Inter. Conf., IEEE, pp. 441\u0026ndash;448\u003c/li\u003e\n\u003cli\u003eLi H, Wang Y, Zhang D, Zhang M, Chang EY (2009) PFP: parallel FP-growth for query recommendation. In: ACM Conference on Recommender Systems, pp. 107\u0026ndash;114\u003c/li\u003e\n\u003cli\u003eGrahne G. and Zhu J. Efficiently Using Prefix-trees in Mining Frequent Itemsets, In Proc. of the IEEE ICDM Workshop on Frequent Itemset Mining, 2004\u003c/li\u003e\n\u003cli\u003eGrahne G, Zhu J (2005) Fast algorithms for frequent itemset mining using FP-trees. IEEE Trans Knowl Data Eng 17(10):1347\u0026ndash;1362. https://doi.org/10.1109/TKDE.2005.166\u003c/li\u003e\n\u003cli\u003eShawkat, M., Badawi, M., El-ghamrawy, S. et al. An optimized FP-growth algorithm for discovery of association rules. J Supercomput 78, 5479\u0026ndash;5506 (2022). https://doi.org/10.1007/s11227-021-04066-y\u003c/li\u003e\n\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"data mining, big data, FP-Growth Tree, association rules","lastPublishedDoi":"10.21203/rs.3.rs-2076910/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-2076910/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eMining data in massive databases to find useful data, frequent patterns (FP) and knowledge discovery, has been studied popularly in data mining research fields minding governments, industries and sales companies. In data mining, frequent patterns as growth tree are an efficient method for discovering knowledge and compressing information in a tree structure. Previous studies presented various methods to achieve frequent patterns which even require complex process and costs, particularly if the patterns overnumbered. In this paper we provide a divide and conquer algorithm based on FP-Growth Tree to create an initially sorted tree structure of the nodes that the most frequent patterns would be available at every moment of the tree construction procedure. In addition, we can consider a parameter to avoid inserting less frequent branches, thus, the tree would be sorted from the beginning of its formation.\u003c/p\u003e","manuscriptTitle":"An Algorithm to Create Sorted FP-Growth Tree for Extracting Association Rules","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2022-09-22 20:37:24","doi":"10.21203/rs.3.rs-2076910/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"70300a74-13f0-415d-8ba2-38b079cf8935","owner":[],"postedDate":"September 22nd, 2022","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2022-09-29T02:59:22+00:00","versionOfRecord":[],"versionCreatedAt":"2022-09-22 20:37:24","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-2076910","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-2076910","identity":"rs-2076910","version":["v1"]},"buildId":"cBFmMYwuxLRRLfASyISRj","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}