Dağıtık sorgu işlemede kaynak atama için çizge merkezilik algoritmaları
Graph centrality algorithms for resource allocation in distributed query processing
Yazar: VEDAT KAVALCI
Danışman: DOÇ. DR. ORHAN DAĞDEVİREN
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı
Derece: Doktora, 2018
Konu: Bilim ve Teknoloji = Science and Technology

Özet:
Bu çalışmada merkezilik tabanlı algoritmaların ve dolayısı ile düğümlere ait ilingesel özelliklerinin sorgu işleme sisteminin performansı üzerine olan etikileri teorik ve pratik olarak incelenmiştir. Öncelikle, bulunabilen dağıtık mimarideki merkezilik algoritmaları analiz edilmiş, sınıflandırılmış ve karmaşık ağlar için uygunlukları araştırılmıştır. Daha sonra, dağıtık sorgu işleme sisteminin ihtiyaçları dikkate alınarak tasarlanan üç adet merkezilik tabanlı kaynak atama algoritması önerilmiştir. Bu algoritmalar, daha doğru adaylarının daha kısa sürede seçilmesini amaçlayan sezgisel yaklaşımlar içermekte ve her biri kendi merkezilik sınıfının en temel özelliklerini taşımaktadır. Son olarak, önerilen algoritmalar ile kodlanan kıyas algoritmalarının teorik ve deneysel analizleri yapılmıştır. 
Gerçek hayat şartları dikkate alınarak yapılan benzetimler sonucunda, önerilen CCBC ile BCBC algoritmaları birbirlerine çok yakın ve en iyi sonuçları vermiştir. Bu durum, yakınlık ve aradalılık merkezilik yaklaşımlarının, kaynak atama sürecinde olumlu ve benzer oranda etkili olduğunu göstermiştir. Buradan yola çıkarak, dağıtık sorgu işleme sistemlerinde, düğümlerin ilingesel özelliklerin oldukça etkili olduğu ve kaynak atama aşamasında kullanılan maliyet modelinde bir parametre olarak kullanılmasının uygun olduğu sonucuna varılmıştır. Ayrıca bu çalışmada önerilen; sınırlı merkezilik yaklaşımı ve altçizge belirleme yaklaşımlarının aday belirleme sürecinde algoritma maliyetlerini olumlu yönde etkilediği gözlenmiştir. Dağıtık sorgu işleme sistemi ile merkezilik hesaplama yöntemleri dikkate alınarak tasarlanan bu yaklaşımlar sadece aday kümesini daraltmakla kalmayıp doğru adayın seçimine de katkı sağlamışlardır.

Abstract:
In this study, the effectiveness of the topological properties of the nodes has been investigated with help of the centrality based algorithms. Firstly, recently distributed centrality algorithms have been analyzed, clustered and investigated their applicability of algorithms to complex networks. Then, three centrality based resource allocation algorithms have been proposed.  These algorithms are designed taking into account the needs of the distributed query processing. Proposed algorithms have some heuristic approaches to be fast and to find correct candidates. Besides, proposed algorithms are good example of their class.  Finally, theoretical and experimental analyzes of the compare and proposed algorithms have been carried out.
 Real-life conditions are taken into consideration in simulation studies. As a result of the simulation studies, the CCBC and BCBC algorithms are very close to each other and gave the best results. This shows that closeness and betweenness centrality approaches have a positive and similar effect on the resource allocation process. Based on this; in distributed query processing systems, it has been concluded that the topological properties of the nodes are very effective and it is appropriate to use them as a parameter in the cost model used in the resource allocation phase. Besides, in this study, proposed limited centrality approach and subgraph detection approaches have been observed to affect the algorithm costs positively in the candidate determination process. These approaches, which are designed by considering the distributed query processing system and centrality calculation methods, not only narrow the candidate cluster but also contribute to the selection of the correct candidate.