Back to Search
Start Over
Hiperçizge tabanlı veri bölümleme
- Publication Year :
- 2013
- Publisher :
- Mühendislik ve Fen Bilimleri Enstitüsü, 2013.
-
Abstract
- 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. 116
- Subjects :
- Partitions (Mathematics)
combinatorial algorithms
Computer graphics
data partitioning
QA165 .K391 2013
hypergraph
Hypergraphs
Combinatorial analysis
Computer Engineering and Computer Science and Control
MathematicsofComputing_DISCRETEMATHEMATICS
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.dedup.wf.001..7d90db4798250f44e1c8d722a93006b6