Replicated hypergraph partitioning

Hiperçizge bölümleme son zamanlarda dağıtık veri erişimi ve uzamsal veri tabanlarında iletişim ve disk erişim maliyetlerini doğru bir sekilde yakalamak için kullanılmıştır. Bu alanlardaki hiperçizge modellerinde, hiperçizge bölümleme kullanılarak elde edilen bölümlerin kalitesi hedeflenen problemin objektifi için çok önemli olabilir. Çoklama, dağıtık veri erişimi ve veri tabanı sistemlerinde çeşitli performans meselelerini ele almak için yaygın olarak kullanılan bir terminolojidir. Çoklamanın arkasındaki ana motivasyon, hedeflenen konunun performansını daha fazla alan kullanma pahasına geliştirmektir.Bu çalışmada, hiperçizge bölümlemenin kalitesini düğüm çoklamasıyla geliştiren hiperçizge bölümleme şemalarının üstüne odaklanıyoruz. Bu aşamada, çoklama ve bölümlemenin bir arada yapıldığı bir çoklamalı hiperçizge bölümleme şeması öneriyoruz. Yaklaşımımız, hiperçizge bölümlemesi için başarılı çok seviyeli ve özyinelemeli ikiye bölümleme yöntemlerini kullanmaktadır. Çoklama, çok seviyeli yöntemin açılma safhasında verimli Fiduccia-Mattheyses (FM) yinelemeli geliştirme sezgiselini genişleterek elde edilmektedir. Bu genişletilmiş versiyona çoklamalı FM (rFM) diyoruz. Önerilen rFM sezgiseli yeni algoritmalar ve köşe durumları öne sürerek taşıma, çoklama ve azlama işlemlerini desteklemektedir. Önerilen çoklama şemasını çok seviyeli hiperçizge bölümleme aracı PaToH'a entegre edip çeşitli gerçekçi veri takımları üstünde test ediyoruz.