Hypergraph-based data partitioning
Hiperçizge tabanlı veri bölümleme
- Tez No: 336862
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- 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: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 116
Özet
Hiperçizgeler, bir kenarın herhangi bir sayıda düğümü bağlayabilme özelliği olduğu, çizgelerin genelleştirilmis bir versiyonudur. Bu genelleme ile hiperçizgeler yüksek bir modelleme gücüne sahiptir öyle ki kombinatöriyel bilimsel hesaplama alanında birçok önemli problem hiperçizgeler ile güçlü bir şekilde modellenebilmektedir. Bu tez ise hiperçizge tabanlı yöntemler kullanılarak veri bölümleme problemlerinin çözülmesini araştırmaktadır. Bu tez üç ana bölümden oluşmaktadır. Birinci bölümde, özyinelemeli çizge ikiye-bölümleme kullanarak, verimli bir hiperçizge bölümlere aracının nasıl oluşturulduğu gösterilmektedir. İkinci ve üçüncü bölümlerde, paralel hesaplamadaki iki önemli veri bölümleme probleminin hiperçizge bölümleme ile nasıl modellendiği gösterilmektedir. Birinci problem paralel sorgu hesaplama için indeksin terim-tabanlı bölümlenmesi problemidir. İkincisi ise yeni önerilen bir paralel matriks vektör çarpımında kullanılmak üzere yine yeni önerilen bir seyrek matriks bölümleme problemidir. Bu tezde, hiperçizge tabanlı modelleri ile daha kaliteli veri bölümleme elde edildiği gösterilmektedir. Anahtar sozcukler: hipercizge, veri bolumleme, kombinatoriyel algoritmalar.
Özet (Çeviri)
A hypergraph is a general version of graph where the edges may connect any number of vertices. By this flexibility, hypergraphs has a larger modeling power that may allow accurate formulaion of many problems of combinatorial scientific computing. This thesis discusses the use of hypergraph-based approaches to solve problems that require data partitioning. The thesis is composed of three parts. In the first part, we show how to implement hypergraph partitioning efficiently using recursive graph bipartitioning. The remaining two parts show how to formulate two important data partitioning problems in parallel computing as hypergraph partitioning. The first problem is global inverted index partitioning for parallel query processing and the second one is row-columnwise sparse matrix partitioning for parallel matrix vector multiplication, where both multiplication and sparse matrix partitioning schemes has novelty. In this thesis, we show that hypergraph models achieve partitions with better quality.
Benzer Tezler
- Hypergraph based declustering of multi-disk databases
Çok diskli veritabanlarının hiperçizge tabanlı ayrıştırılması
MEHMET KOYUTÜRK
Yüksek Lisans
İngilizce
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- A Hypergraph-partitioning based remapping model for image-space parallel volume rendering
Görüntü-uzayı paralel hacim görüntüleme için hiperçizge bölümlemeye dayalı yeniden eşleme modeli
BERKANT BARLA
Yüksek Lisans
İngilizce
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Exploiting replicated data for communication load balancing in image-space parallel direct volume rendering of unstructured grids
Düzensiz ızgaralarda görüntü-uzayı paralel hacim görüntüleme için iletişim yükü eşitlemede kopyalanmış veriden faydalanma
ERKAN OKUYAN
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Storage and access schemes for aggregate query processing on road networks
Yol ağları üzerindeki topak sorgu işleme için depolama ve erişim planları
ENGİN DEMİR
Doktora
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Combinatorial reductions between graph partitioning by vertex separator and hypergraph partitioning problems for parallel and scientific computing applications
Paralel ve bilimsel hesaplama uygulamaları için hiperçizge bölümleme ve düğüm ayıracı ile çizge bölümleme problemlerinin birbirine kombinatoriyal dönüştürümü
ENVER KAYAASLAN
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT