Balance preserving min-cut replication set for a K-way hypergraph partitioning

Çoklama, veri erişimi ve veritabanı sistemlerinde aksaklığa dayanıklılık ve paralelizasyon ve işleme yüklerinin azaltılması için sıkça kullanılan bir tekniktir. Veri erişimi ve veritabanı sistemlerinde hiperçizge bölümlemesine dayanan bir çok kombinasyonel model önerilmiştir. Bu çalışmada, düğüm çoklamaları kullanılarak hiperçizge bölümlemelerindeki kesit boyutunun azaltılması üzerinde durmaktayız. Bu amaçla, verilen bir maksimum çoklama kapasitesi ve K parçalı hiperçizge bölümlemesi ile Denge Korumalı Min-Kesit Çoklama Kümesi'nin (DKMKÇK) bulunması problemi üzerine yoğunlaşmaktayız. DKMKÇK probleminde amaç, her parça için bulunacak bir çoklama kümesi ile baştaki bölümlemenin dengesini koruyarak kesit boyutunu azaltmaktır. Bu amaçla, küçültme (coarsening) ve tamsayı doğrusal programlama (integer linear programming (ILP)) yöntemlerinin seçkin bileşiminden oluşan bir model öneriyoruz. Modelde kullanılan küçültme algoritması Dulmage-Mendelsohn ayrışımına dayanmaktadır. Yapılan deneylerde, Dulmage-Mendelsohn ayrışımına dayalı küçültme yöntemi ile birlikte kullanılan ILP formülasyonunun mantıklı çalışma zamanları içinde, verilen bir K parçalı hiperçizge bölümlemesinin kesit boyutunu düğüm çoklamaları ile oldukça yüksek seviyelerde azalttığı gözlemlenmiştir.