Journals / Politeknik Dergisi / 2021 / Cilt: 24 - Sayı: 1

A New Approach to Minimize Memory Requirements of Frequent Subgraph Mining Algorithms

Pages
237–246
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Almost all results show that the proposed implementation consumes less memory on each support level.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Frequent subgraph mining (FSM) is a subsection of graph mining domain which is extensively used for graph classification and graph clustering purposes.
📊
Key Findings & Data:Over the past decade, many efficient FSM algorithms have been developed.
💡
Conclusion & Impact:Almost all results show that the proposed implementation consumes less memory on each support level.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Frequent subgraphs · data mining · space complexity

Abstract

Frequent subgraph mining (FSM) is a subsection of graph mining domain which is extensively used for graph classification and graph clustering purposes. Over the past decade, many efficient FSM algorithms have been developed. The improvements generally focus on reducing time complexity by changing the algorithm structure or using parallel programming techniques. FSM algorithms have another problem to solve, which is the high memory consumption. In this study, a new approach called Predictive Dynamic Sized Structure Packing (PDSSP) have been proposed to minimize the memory requirement of FSM algorithms. Proposed approach redesigns the internal data structures of FSM algorithms without any algorithmic modifications. PDSSP has two contributions. The first one is the Dynamic Sized Integer Type (ds_Int) which is a newly designed unsigned integer data type. The second contribution is “Data Structure packaging” component that uses a data structure packing technique which changes the behaviour of the compiler. A number of experiments have been conducted to examine the effectiveness and efficiency of the PDSSP approach by embedding it into two state-of-art algorithms called gSpan and Gaston. Proposed implementation have been compared to the official one. Almost all results show that the proposed implementation consumes less memory on each support level. As a result, PDSSP extensions can save memory and the peak memory usage may decrease up to 38% depending on the dataset.

Özet

Frequent subgraph mining (FSM) is a subsection of graph mining domain which is extensively used for graph classification and graph clustering purposes. Over the past decade, many efficient FSM algorithms have been developed. The improvements generally focus on reducing time complexity by changing the algorithm structure or using parallel programming techniques. FSM algorithms have another problem to solve, which is the high memory consumption. In this study, a new approach called Predictive Dynamic Sized Structure Packing (PDSSP) have been proposed to minimize the memory requirement of FSM algorithms. Proposed approach redesigns the internal data structures of FSM algorithms without any algorithmic modifications. PDSSP has two contributions. The first one is the Dynamic Sized Integer Type (ds_Int) which is a newly designed unsigned integer data type. The second contribution is “Data Structure packaging” component that uses a data structure packing technique which changes the behaviour of the compiler. A number of experiments have been conducted to examine the effectiveness and efficiency of the PDSSP approach by embedding it into two state-of-art algorithms called gSpan and Gaston. Proposed implementation have been compared to the official one. Almost all results show that the proposed implementation consumes less memory on each support level. As a result, PDSSP extensions can save memory and the peak memory usage may decrease up to 38% depending on the dataset.

🔖

Cite This Article

BİLGİN, T. T., BİLGİN, T. T. (2021). A New Approach to Minimize Memory Requirements of Frequent Subgraph Mining Algorithms. Politeknik Dergisi, Cilt: 24 - Sayı: 1, 237–246. https://ajindex.com/articles/307355

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (12)

  1. Thusoo A, Shao Z, Anthony S, Borthakur D, Jain N, Sen Sarma J, Murthy R, Liu H. “Data warehousing and analytics infrastructure at Facebook”. In: ACM SIGMOD/PODS 2010 Conference; Indianapolis, Indiana, USA: ACM. pp. 1013–1020, 2010
  2. Wang L, Xiao Y, Shao B, Wang H. “How to partition a billion-node graph”. In: IEEE 2014 International Conference on Data Engineering; Chicago, IL, USA: IEEE; pp. 568–579, 2014 [3] Muttipati AS, Padmaja P. “Analysis of large graph partitioning and frequent subgraph mining on graph data”. International Journal of Advanced Research in Computer Science 2015; pp. 6-7, 2015
  3. G. V. Carlos, M. Esteban, “Comparative Analysis of de Bruijn Graph Parallel Genome Assemblers”, 2018 IEEE International Work Conference on Bioinspired Intelligence (IWOBI), IEEE, pp 1-8, 2018
  4. Talukder, N. and Zaki, M.J., “A distributed approach for graph mining in massive networks”. Data Mining and Knowledge Discovery, 30(5), pp.1024-1052, 2016
  5. Di Fatta, G., & Berthold, M. R. “High performance subgraph mining in molecular compounds”. In International Conference on High Performance Computing and Communications, Springer, Berlin, Heidelberg.,pp. 866-877, (2005, September)
  6. Stratikopoulos A, Chrysos G, Papaefstathiou I, Dollas A. “HPC-gSpan: An FPGA-based parallel system for frequent subgraph mining”. In IEEE 2014 24th International Conference on Field Programmable Logic and Applications (FPL); Munich, Germany, IEEE. pp. 1-4, 2014
  7. Aggarwal CC, Bhuiyan MA, Al Hasan M. “Frequent pattern mining algorithms: A survey”. In: Aggarwal CC, Han J, editors. Frequent Pattern Mining. Switzerland: Springer International Publishing, pp. 19–64, 2014
  8. Anastasiu DC, Iverson J, Smith S, Karypis G. “Big data frequent pattern mining”. In: Aggarwal CC, Han J, editors. Frequent Pattern Mining. Switzerland: Springer International Publishing, pp. 225–259, 2014
  9. Yan X, Han J. “gSpan: Graph-based substructure pattern mining”. In: IEEE 2003 International Conference on Data Mining; Melbourne, Florida, USA: IEEE. pp. 721–724, 2003
  10. Nijssen S, Kok JN. “The Gaston tool for frequent subgraph mining”. Electronic Notes in Theoretical Computer Science, pp 127;77–87, 2005
  11. Yan X, Han J. “CloseGraph: Mining closed frequent graph patterns”. In: ACM SIGKDD 2003 International Conference on Knowledge Discovery and Data Mining; Washington, DC, USA: ACM. pp. 286–295, 2003
  12. Lakshmi K, Meyyappan DT. “A comparative study of frequent subgraph mining algorithms