Bilkent University
Department of Computer Engineering

---

Ph.D Dissertation

 

Hypergraph-Partitioning-Based Data Partitioning

 

Enver Kayaaslan
PhD Student
Computer Engineering Department
Bilkent University

Hypergraph is a generalization of graph as it replaces edges that connect only two vertices with hyperedges (nets) that can connect any positive number of vertices. This generalization provides a critical modeling flexibility that allows accurate formulation of many important problems in combinatorial scientific computing. This thesis discusses hypergraph-partitioning-based approaches to solve problems that require data partitioning. The thesis is composed of three parts.

The first part shows how to formulate and implement a fast hypergraph partitioning using recursive graph bipartitioning. The second part shows how to formulate inverted list distribution to processors as a hypergraph partitioning problem for parallel query processing on global inverted index partitioning scheme. The third part shows how to formulate row-columnwise sparse matrix partitioning, which is proposed for a novel sparse matrix vector multiplication scheme that require single communication phase with more flexibility on the distribution of nonzeros, as a dependent hypergraph partitioning problem which is a restricted version of hypergraph partitioning problem.

 

DATE: 12 September, 2013, Thursday @ 10:00
PLACE: EA-409