Sık Alt Çizge Madenciliği Algoritmalarının Bellek Gereksinimlerini En Aza İndirmek İçin Yeni Bir Yaklaşım

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

Özet

Sık alt çizge madenciliği (SAÇM), çizge sınıflandırma ve çizge kümeleme için yaygın olarak kullanılan bir çizge madenciliği alt türüdür. Son on yılda, birçok verimli SAÇM algoritması geliştirilmiştir. Geliştirmeler genellikle algoritma yapısını değiştirerek veya paralel programlama teknikleri kullanarak zaman karmaşıklığını azaltmaya odaklanmıştır. SAÇM algoritmalarının çözülmesi gereken en önemli problemlerinden biri yüksek bellek tüketimidir. Bu çalışmada, SAÇM algoritmalarının bellek gereksinimini en aza indirmek için Öngörücü Dinamik Boyutlu Yapı Paketleme (ÖDBYP) adı verilen yeni bir yaklaşım önerilmiştir. Önerilen yaklaşım SAÇM algoritmalarının iç veri yapılarında herhangi bir algoritmik değişiklik yapmadan yeniden tasarlamaya olanak sağlamaktadır. Bu çalışma kapsamında geliştirilen ÖDBYP ile very madenciliği alanına iki önemli katkı sağlanmaktadır. Birincisi, yeni tasarlanmış işaretsiz bir tamsayı veri türü olan Dinamik Boyutlu Tamsayı Türüdür (ds_Int). İkinci katkı, derleyicinin davranışını değiştiren bir veri yapısı paketleme tekniği kullanan “Veri Yapısı paketleme” bileşenidir. ÖDBYP yaklaşımının etkinliğini ve verimliliğini, gSpan ve Gaston adlı güncel algoritmalara gömerek çeşitli deneyler gerçekleştirilmiştir. Çalışma kapsamında geliştirilen yöntem ile algoritmaların original halleri ile kıyaslanmıştır. Neredeyse tüm sonuçlar, önerilen uygulamanın her destek düzeyinde daha az bellek harcadığını göstermektedir. Sonuç olarak, ÖDBYP uzantıları bellek tasarrufu sağlayabilir ve veri kümesine bağlı olarak maksimum bellek kullanımı % 38 kadar düşürülebilmektedir.

Abstract

Frequent subgraph mining (FSM) is a subsection of graph mining domain which is extensively used for graph classification andgraph clustering purposes. Over the past decade, many efficient FSM algorithms have been developed. The improvements generallyfocus on reducing time complexity by changing the algorithm structure or using parallel programming techniques. FSM algorithmshave another problem to solve, which is the high memory consumption. In this study, a new approach called Predictive DynamicSized Structure Packing (PDSSP) have been proposed to minimize the memory requirement of FSM algorithms. Proposed approachredesigns the internal data structures of FSM algorithms without any algorithmic modifications. PDSSP has two contributions. Thefirst one is the Dynamic Sized Integer Type (ds_Int) which is a newly designed unsigned integer data type. The second contributionis “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 embeddingit 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, PDSSPextensions can save memory and the peak memory usage may decrease up to 38% depending on the dataset.