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