Parallel Frequent Subtrees Mining Method by an Effective Edge Division Strategy
Source abstract
Abstract
Most data with a complicated structure can be represented by a tree structure. Parallel processing is essential to mining frequent subtrees from massive data in a timely manner. However, only a few algorithms could be transplanted to a parallel framework. A new parallel algorithm is proposed to mine frequent subtrees by grouping strategy (GS) and edge division strategy (EDS). The main idea of GS is dividing edges according to different intervals and then dividing subtrees consisting of the edges in different intervals to their corresponding groups. Besides, the compression stage in mining is optimized by avoiding all candidate subtrees of a compression tree, which reduces the mining time on the nodes. Load balancing can improve the performance of parallel computing. An effective EDS is proposed to achieve load balancing. EDS divides the edges with different frequencies into different intervals reasonably, which directly affects the task amount in each computing node. Experiments demonstrate that the proposed algorithm can implement parallel mining, and it outperforms other compared methods on load balancing and speedup.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Data Mining Algorithms and Applications · Rough Sets and Fuzzy Logic · Data Management and Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Media Science, Northeast Normal University, Changchun 130024, China
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
Funding
Technology Development Plan of Jilin Province · Fundamental Research Funds for the Central Universities
References (30)
Show source-provided references
1. A survey on semi-structured web data manipulations by non-expert users10.1016/j.cosrev.2021.100367 ↗
2. Du, Y. (2021). Massive Semi-structured Data Platform Based on Elasticsearch and MongoDB. Signal and Information Processing, Networking and Computers, Springer.10.1007/978-981-33-4102-9_105 ↗
3. Hong, T.P., Lin, C.Y., Huang, W.M., Li, S.M., Wang, S.L., and Lin, J.C. (2022). A One-Phase Tree-Structure Method to Mine High Temporal Fuzzy Utility Itemsets. Appl. Sci., 12.10.3390/app12062821 ↗
4. Advanced uncertainty based approach for discovering erasable product patterns10.1016/j.knosys.2022.108134 ↗
5. Valid Plane Trees: Combinatorial Models for RNA Secondary Structures with Watson–Crick Base Pairs10.1137/15M1008841 ↗
6. Welke, P. (2020). Efficient Frequent Subtree Mining Beyond Forests, IOS Press.
7. Finding good subtrees for constraint optimization problems using frequent pattern mining
8. Integrating Cuckoo search-Grey wolf optimization and Correlative Naive Bayes classifier with Map Reduce model for big data classification10.1016/j.datak.2019.101788 ↗
9. Research on a frequent maximal induced subtrees mining method based on the compression tree sequence10.1016/j.eswa.2014.07.053 ↗
10. Energy-efficient acceleration of MapReduce applications using FPGAs10.1016/j.jpdc.2018.02.004 ↗
11. Es-Sabery, F., and Hair, A. (April, January 31). Big data solutions proposed for cluster computing systems challenges: A survey. Proceedings of the 3rd International Conference on Networking, Information Systems & Security, Marrakech, Morocco.
12. Data mining for the internet of things: Literature review and challenges10.1155/2015/431047 ↗
13. Mining frequent itemsets using the N-list and subsume concepts10.1007/s13042-014-0252-2 ↗
14. PFIMD: A parallel MapReduce-based algorithm for frequent itemset mining10.1007/s00530-020-00725-x ↗
15. Welke, P., Seiffarth, F., Kamp, M., and Wrobel, S. (2020, January 23–27). HOPS: Probabilistic subtree mining for small and large graphs. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual Event, CA, USA.10.1145/3394486.3403180 ↗
16. Mining temporal association rules with frequent itemsets tree10.1016/j.asoc.2017.09.013 ↗
17. Huynh, V., and Küng, J. (2018, January 28–30). Higher Performance IPPC+ Tree for Parallel Incremental Frequent Itemsets Mining. Proceedings of the 5th International Conference FDSE, Ho Chi Minh City, Vietnam.10.1007/978-3-030-03192-3_10 ↗
18. Probabilistic and exact frequent subtree mining in graphs beyond forests10.1007/s10994-019-05779-1 ↗
19. Wang, C.S., and Chang, J.Y. (2019). MISFP-Growth: Hadoop-Based Frequent Pattern Mining with Multiple Item Support. Appl. Sci., 9.10.3390/app9102075 ↗
20. Prediction of multicore CPU performance through parallel data mining on public datasets10.1016/j.displa.2021.102112 ↗
21. The rise of big data on cloud computing: Review and open research issues10.1016/j.is.2014.07.006 ↗
22. Shaik, S., Subhani, S., Devarakonda, N., and Nagamani, C. (2017, January 14–15). Parallel Computing Algorithms for Big data frequent pattern mining. Proceedings of the International Conference on Computational Intelligence & Data Engineering ICCIDE, Vijayawada, India.10.1007/978-981-10-6319-0_10 ↗
23. Yan, D., Qu, W., Guo, G., and Wang, X. (2020, January 20–24). PrefixFPM: A Parallel Framework for General-Purpose Frequent Pattern Mining. Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE), Dallas, TX, USA.10.1109/ICDE48307.2020.00208 ↗
24. PrefixFPM: A parallel framework for general-purpose mining of frequent and closed patterns10.1007/s00778-021-00687-0 ↗
25. Fidoop: Parallel mining of frequent itemsets using mapreduce10.1109/TSMC.2015.2437327 ↗
26. An effective parallel approach for genetic-fuzzy data mining10.1016/j.eswa.2013.07.090 ↗
27. Finding tendencies in streaming data using Big Data frequent itemset mining10.1016/j.knosys.2018.09.026 ↗
28. Sicard, N., Laurent, A., López, F.D., and Flores, P.M. (2010, January 18–23). Towards multi-core parallel fuzzy tree mining. Proceedings of the 2010 IEEE International Conference on Fuzzy Systems (FUZZ), Barcelona, Spain.10.1109/FUZZY.2010.5584833 ↗
29. Efficiently Mining Frequent Trees in a Forest: Algorithms and Applications10.1109/TKDE.2005.125 ↗
30. A comparison of parallel large-scale knowledge acquisition using rough set theory on different MapReduce runtime systems10.1016/j.ijar.2013.08.003 ↗