Page 15 - KATALOG Çalışması 2020

Bilgisayar Mühendisliği ABD Yüksek Lisans Programı Computer Engineering Majors in Master of Science

Tez Başlığı Thesis Title
İKİ PARÇALI ÇİZGELERDE ETKİN ALT-ÇİZGE ARAMASI EFFICIENT SUBGRAPH SEARCH IN BIPARTITE GRAPHS
Öğrenci Adı / Student’s Name Mehmet Burak KOCA

Tez Danışmanı / Thesis Supervisor Prof. Dr. Fatih Erdoğan SEVİLGEN
Eş-Danışman / Co-Advisor

ÖZET ABSTRACT

Alt-çizge eşbiçimlilik probleminin çözümü için 70’li yıllardan beri çalışmalar yapılsa Although there have been studies since 1970s for the subgraph isomorphism problem, new
da çizge boyutlarındaki artış sebebiyle yeni yöntemler yayımlanmaya devam etmekte methods continue to be published because the problem is still popular due to the increase
ve problem popülerliğini korumaktadır. Artan çizge boyutları ile baş edebilmek için in the graph size. There are a lot of algorithms that exploit structural and semantic
birçok algoritma çizgelerin yapısal ve anlamsal özelliklerinden faydalanmaktadır fakat attributes of the graphs to handle the increase in the graph size but only a few of them
sadece birkaçı çizgelerin karakteristik özelliğini hesaba katmaktadır. Genel çizgeleri consider graph characteristics. The approaches that aim the general graphs can do
hedef alan yaklaşımlar tüm çizge türleri üzerinde eşbiçimlilik sorgusu yapabilmekte subgraph isomorphism search on all graph types, but they can’t benefit from obtainable
fakat özel çizgelere has özelliklerin kullanılmasıyla elde edilebilecek faydalardan advantages by using idiosyncrasies of some special graphs. The subgraph isomorphism
mahrum kalmaktadırlar. Özel bir çizge türü olan iki parçalı çizgeler üzerinde alt-çizge problem in bipartite graphs, a special graph type, is an open research area. Comprehensive
eşbiçimlilik problemi açık bir araştırma alanıdır: Bildiğimiz kadarıyla, şimdiye kadar literature search show that, as far as we know, there is no algorithm for the solution of the
iki parçalı çizgeler için özelleştirilmiş alt-çizge eşbiçimlilik algoritması problem in the bipartite graphs. Within the scope of this thesis study, novel exact and in-
bulunmamaktadır. Tez çalışması kapsamında, iki parçalı çizgelerin karakteristik exact algorithms with high performance are proposed for the solution of the problem on
özelliklerinden faydalanarak alt-çizge eşbiçimlilik problemini bu çizgelerde daha these type graphs by exploiting graph characteristic of bipartite graphs. Two exact match
yüksek performans ile çözebilen özgün birebir ve yaklaşık eşleme algoritmaları algorithms have been proposed in this thesis study. One of the algorithms is based on
geliştirilmiştir. Bu tez çalışmasında birebir eşleme yapan iki farklı algoritma branch-and-bound approach. The algorithm has a powerful pruning technique thanks to the
sunulmaktadır. Algoritmalardan biri dal-ve-sınır yaklaşımına sahiptir. Bu algoritma, partitioned structure of bipartite graphs. It can prune infeasible branches before they are
iki parçalı yapının sağladığı imkân doğrultusunda güçlü bir budama tekniğine sahiptir generated. Another proposed exact matching algorithm is an index-based solution. The
ve bu sayede uygunsuz dallanmalar daha oluşmadan budanmaktadır. Diğer birebir algorithm only indexes necessary data and provides efficient filtering by using triplets as
eşleme algoritması indeks tabanlı bir yaklaşıma sahiptir. Algoritma iki parçalı çizgelere index structure. Triplets are very suitable for the bipartite graphs and they allow to do
uygun kazayağı indeks yapısını kullanarak uygunsuz parçadaki indeks ögelerini efficient indexing and filtering. The last algorithm allows performing approximate subgraph
filtreleme imkânı sağlar. Geliştirilen son algoritma indeks tabanlı algoritmaya ayrıt isomorphism search in bipartite graphs with high-performance. All the three proposed
eksikliği üzerinden esneklik sağlayarak yaklaşık alt-çizge eşleme işlemini yüksek algorithms have been compared with their state-of-art competitors. The proposed
performans ile gerçekleştirmeyi sağlamaktadır. Geliştirilen üç algoritma da literatürde algorithms show two to a thousand-time better run-time performance results for various
bulunan aynı türdeki yüksek performanslı algoritmalar ile karşılaştırmalı performans graph sizes or densities.
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.
Anahtar Kelimeler / Key-words Alt-çizge Eşbiçimlilik, İki Parçalı Çizgeler, Birebir Eşleme, Yaklaşık Eşleme.

Tez Numarası / Thesis Number 620515