Çoklamalı hiperçizge bölümleme

Hypergraph partitioning is recently used in distributed information retrieval (IR)and spatial databases to correctly capture the communication and disk accesscosts. In the hypergraph models for these areas, the quality of the partitionsobtained using hypergraph partitioning can be crucial for the objective of thetargeted problem. Replication is a widely used terminology to address differentperformance issues in distributed IR and database systems. The main motivationbehind replication is to improve the performance of the targeted issue at the costof using more space.In this work, we focus on replicated hypergraph partitioning schemes that im-prove the quality of hypergraph partitioning by vertex replication. To this end,we propose a replicated partitioning scheme where replication and partitioningare performed in conjunction. Our approach utilizes successful multilevel andrecursive bipartitioning methodologies for hypergraph partitioning. The repli-cation is achieved in the uncoarsening phase of the multilevel methodology byextending the efficient Fiduccia-Mattheyses (FM) iterative improvement heuris-tic. We call this extended heuristic replicated FM (rFM). The proposed rFMheuristic supports move, replication and unreplication operations on the verticesby introducing new algorithms and vertex states. We show rFM has the samecomplexity as FM and integrate the proposed replication scheme into the mul-tilevel hypergraph partitioning tool PaToH. We test the proposed replicationscheme on realistic datasets and obtain promising results.