İki parçalı çizgelerde etkin alt-çizge araması

Abstract

Alt-çizge eşbiçimlilik probleminin çözümü için 70'li yıllardan beri çalışmalar yapılsa da çizge boyutlarındaki artış sebebiyle yeni yöntemler yayımlanmaya devam etmekte ve problem popülerliğini korumaktadır. Artan çizge boyutları ile baş edebilmek için birçok algoritma çizgelerin yapısal ve anlamsal özelliklerinden faydalanmaktadır fakat sadece birkaçı çizgelerin karakteristik özelliğini hesaba katmaktadır. Genel çizgeleri hedef alan yaklaşımlar tüm çizge türleri üzerinde eşbiçimlilik sorgusu yapabilmekte fakat özel çizgelere has özelliklerin kullanılmasıyla elde edilebilecek faydalardan mahrum kalmaktadırlar.Özel bir çizge türü olan iki parçalı çizgeler üzerinde alt-çizge eşbiçimlilik problemi açık bir araştırma alanıdır: Bildiğimiz kadarıyla, şimdiye kadar iki parçalı çizgeler için özelleştirilmiş alt-çizge eşbiçimlilik algoritması bulunmamaktadır. Tez çalışması kapsamında, iki parçalı çizgelerin karakteristik özelliklerinden faydalanarak alt-çizge eşbiçimlilik problemini bu çizgelerde daha yüksek performans ile çözebilen özgün birebir ve yaklaşık eşleme algoritmaları geliştirilmiştir.Bu tez çalışmasında birebir eşleme yapan iki farklı algoritma sunulmaktadır. Algoritmalardan biri dal-ve-sınır yaklaşımına sahiptir. Bu algoritma, iki parçalı yapının sağladığı imkân doğrultusunda güçlü bir budama tekniğine sahiptir ve bu sayede uygunsuz dallanmalar daha oluşmadan budanmaktadır. Diğer birebir eşleme algoritması indeks tabanlı bir yaklaşıma sahiptir. Algoritma iki parçalı çizgelere uygun kazayağı indeks yapısını kullanarak uygunsuz parçadaki indeks ögelerini filtreleme imkânı sağlar. Geliştirilen son algoritma indeks tabanlı algoritmaya ayrıt eksikliği üzerinden esneklik sağlayarak yaklaşık alt-çizge eşleme işlemini yüksek performans ile gerçekleştirmeyi sağlamaktadır. Geliştirilen üç algoritma da literatürde bulunan aynı türdeki yüksek performanslı algoritmalar ile karşılaştırmalı performans testine tabi tutulmuştur. Sonuçlarda, geliştirilen algoritmaların rakiplerine oranla, çizgelerin düğüm ve ayrıt sayısına göre, iki ile bin kat arasında daha iyi performans gösterdiği gözlemlenmiştir.

Although there have been studies since 1970s for the subgraph isomorphism problem, new methods continue to be published because the problem is still popular due to the increase in the graph size. There are a lot of algorithms that exploit structural and semantic attributes of the graphs to handle the increase in the graph size but only a few of them consider graph characteristics. The approaches that aim the general graphs can do subgraph isomorphism search on all graph types, but they can't benefit from obtainable advantages by using idiosyncrasies of some special graphs.The subgraph isomorphism problem in bipartite graphs, a special graph type, is an open research area. Comprehensive literature search show that, as far as we know, there is no algorithm for the solution of the problem in the bipartite graphs. Within the scope of this thesis study, novel exact and in-exact algorithms with high performance are proposed for the solution of the problem on these type graphs by exploiting graph characteristic of bipartite graphs.Two exact match algorithms have been proposed in this thesis study. One of the algorithms is based on branch-and-bound approach. The algorithm has a powerful pruning technique thanks to the partitioned structure of bipartite graphs. It can prune infeasible branches before they are generated. Another proposed exact matching algorithm is an index-based solution. The algorithm only indexes necessary data and provides efficient filtering by using triplets as index structure. Triplets are very suitable for the bipartite graphs and they allow to do efficient indexing and filtering. The last algorithm allows performing approximate subgraph isomorphism search in bipartite graphs with high-performance. All the three proposed algorithms have been compared with their state-of-art competitors. The proposed algorithms show two to a thousand-time better run-time performance results for various graph sizes or densities.