İki parçalı çizgelerde etkin alt-çizge araması
Efficient subgraph search in bipartite graphs
- Tez No: 620515
- Danışmanlar: PROF. DR. FATİH ERDOĞAN SEVİLGEN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: Türkçe
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 97
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Etkin sorgu önerileri için kullanıcı sorgularının görev tabanlı yönetilmesi
Task based management of user queries for effective query suggestions
NURULLAH ATEŞ
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. YUSUF YASLAN
- Karikatürün tarihi ve karikatürün grafik sanatlarla ilişkisi
Başlık çevirisi yok
BORA ÖZEN
Yüksek Lisans
Türkçe
2003
Güzel SanatlarMarmara ÜniversitesiGrafik Ana Sanat Dalı
YRD. DOÇ. DR. GÜRBÜZ DOĞAN EKŞİOĞLU
- Bilişim sistemlerindeki gelişmelerin işletme yönetimine etkileri, yönetim bilişim sistemleri geliştirme ve bir uygulama örneği
Effects of the evoluation of information systems on management, management information systems development and an example of its application
ZUHAL TANRIKULU
Doktora
Türkçe
1999
İşletmeİstanbul ÜniversitesiOrganizasyon ve İşletme Politikaları Ana Bilim Dalı
PROF. DR. EROL EREN
- ISO 19650 compliant project information protocol proposal for collaborative working and BIM execution
İşbirlikçi çalışma ve BIM uygulamaları için ISO 19650 uyumlu proje bilgi protokolü önerisi
SALİM BURAK TEZGİDEN
Yüksek Lisans
İngilizce
2019
Bilgi ve Belge Yönetimiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ ARTAN