Tez No	İndirme	Tez Künye	Durumu
336862		Hypergraph-based data partitioning / Hiperçizge tabanlı veri bölümleme Yazar:ENVER KAYAASLAN Danışman: PROF. DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Hiperçizgeler = Hypergraphs	Onaylandı Doktora İngilizce 2013 116 s.
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.
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.