Distributed database design with integer linear programming and evolutionary hybrid algorithms
Sayısal lineer programlama ve buluşsal hibrit algoritmalar ile dagıtık veritabanı tasarımı
- Tez No: 338499
- Danışmanlar: DOÇ. DR. AHMET COŞAR
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Sorgular tarafından tablo parçalarına uzaktan erişim ve bulunan lokasyona getirme sonucu ortaya çıkan haberleşme maliyeti dağıtık veritabanı sorgularındaki temel işletim maliyetini oluşturmaktadır. Veri yerleştirme algoritmaları bu maliyeti parçaları yakın yerleşim birimlerine atayarak minimuma indirmeye çalışır. Paralel işleme ve sayısal lineer programlama uygulamalarının artması ile veri yerleştirme ve çoklu sorgu optimizasyonu problemlerini modellemeye olan ihtiyaç daha önemli hale gelmiştir. Bu tezde merkezi ve dağıtık veritabanları için sayısal lineer programlama ve iyi bilinen Karesel Atama Problemi (KAP) tabanlı algoritmalar sunulmaktadır. Dağıtık veritabanı tasarımı kapsamında da tesis kapasitesi, tablo replikaları, haberleşme hatları ve tablo parçaları olan ağ topolojilerine konsantre olunmuştur. Bir çok sistem bu gerçek hayatta bulunan faktörlerin bir yada birden fazlasını ihmal ederken, sayısal lineer programlama bu kriterlerin hepsini kolaylıkla güçlü bir şekilde ifade edebilmektedir. İlk defa sayısal lineer programlama ile bütün bu kriterleri uygun bir şekilde ele alan bir model geliştirilmiştir. KAP, kombinatoryal optimizasyon alanında çalışılan önemli ve güç bir problem çeşididir. 10-20 tesisli KAP örneklerini paralel algoritmalarla birkaç gün içerisinde küme bilgisayarlarda tüm olasılıkları deneyerek çözmek mümkündür. 100 tesis gibi büyük KAP örneklerini tüm olasılıkları deneyerek çözmek pratik olarak mümkün değildir. Bu çalışma kapsamında bir çok Genetik Algoritma çaprazlama operatörü araştırılmış ve deneysel olarak performansları QAPLIB kütüphanesinin bilinen örnekleri üzerinde denenmiştir. Genetik algoritmayı paralelize etmek için her küme işlemcisinde ada modeli kullanılarak ayrı havuzlar oluşturulmuş ve geliştirilmiştir. Bu tezde genetik algoritma bazlı üretilen tohum üzerinde akıllı çeşitlendirme fazı çalıştırarak oluşan yeni bir paralel hibrit genetik tabu araması algoritması (PHGTA) sunulmaktadır.
Özet (Çeviri)
The communication costs of remote access and retrieval of table fragments required in the execution of distributed database queries, are the major factors determining the quality of a distributed database design. Data allocation algorithms try to minimize these costs by dividing database tables into horizontal fragments, then assigning each fragment at or near the database sites they are needed more frequently. In this thesis, we propose efficient optimization algorithms for centralized and distributed databases based on integer linear programming and the well known Quadratic Assignment Problem (QAP). In the context of distributed database design, we have formulated an optimization problem where site capacities, table replicas, communication link capacities and table fragmentation are handled. Integer linear programming is a powerful tool to represent all of these optimization parameters easily while existing models in the literature ignore one or more of these important and practical aspects. The proposed model is based on integer linear programming and for the first time it handles all of these criteria in a consistent formulation. The QAP is a difficult and important problem studied in the domain of combinatorial optimization. It is possible to solve QAP instances with 10-20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. We solve large QAP instances using a variety of genetic algorithm crossover operators for these problems and experimentally verified their performance using benchmark QAP instances from QAPLIB library. We propose and experimentally evaluate the island parallel QAP-IPGA algorithm. Then, we propose a new Parallel Hybrid Genetic Tabu Search based algorithm (PHGETS) which has an intelligent diversification phase executed on a seed solution obtained using the genetic algorithm.
Benzer Tezler
- SQL/DS ve CSP/AD ile kütüphane uygulaması geliştirme
Design and implementation of a library application with SQL/DS and CSP/AD
İSRAFİL AVCI
Yüksek Lisans
Türkçe
1990
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT ÖRENCİK
- Yerel yönetimlerde coğrafi bilgi sistemi destekli proje planlaması ve yönetimi
Başlık çevirisi yok
ERKAN BEŞDOK
Yüksek Lisans
Türkçe
1998
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiJeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÖNÜL TOZ
- Dağıtılmış veri yönetimi
Başlık çevirisi yok
HIRAÇ KASAPOĞLU
Yüksek Lisans
Türkçe
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. NADİA ERDOĞAN
- Aktör yapısına dayalı paralel programlama ortamının tasarımı ve gerçeklenmesi
Design and implementation of a parallel programming environment based on actors
MAHMUT TAYLAN KANDEMİR
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ. DR. TAKUHİ NADİA ERDOĞAN
- Bulut tabanlı otonom sürüş sıstemlerınde görüntü işleme ıçın tam homomorfık şıfreleme yaklaşımı
A fully homomorphic encryption approach to image processing in cloud based autonomous driving systems
KAMRAN SAEED
Doktora
Türkçe
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUHAMMED FATİH ADAK