Geri Dön

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

K parçalı bir hiperçizge bölümlemesi için denge korumalı min-kesit çoklama kümesi

  1. Tez No: 275103
  2. Yazar: VOLKAN YAZICI
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 57

Özet

Ç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.

Özet (Çeviri)

Replication is a widely used technique in information retrieval and database systems for providing fault-tolerance and reducing parallelization and processing costs. Combinatorial models based on hypergraph partitioning are proposed for various problems arising in information retrieval and database systems. We consider the possibility of using vertex replication to improve the quality of hypergraph partitioning. In this study, we focus on the Balance Preserving Min-Cut Replication Set (BPMCRS) problem, where we are initially given a maximum replication capacity and a K-way hypergraph partition with an initial imbalance ratio. The objective in the BPMCRS problem is nding optimal vertex replication sets for each part of the given partition such that the initial cutsize of the partition is improved as much as possible and the initial imbalance is either preserved or reduced under the given replication capacity constraint. In order to address the BPMCRS problem, we propose a model based on a unique blend of coarsening and integer linear programming (ILP) schemes. This coarsening algorithm is based on the Dulmage-Mendelsohn decomposition. Experiments show that the ILP formulation coupled with the Dulmage-Mendelsohn decomposition-based coarsening provides high quality results in feasible execution times for reducing the cost of a given K-way hypergraph partition.

Benzer Tezler

  1. Mikro ark oksidasyon işlemi uygulanmış silisyum karbür takviyeli az91d magnezyum alaşımının korozyon ve aşınma özelliklerinin incelenmesi

    Investigation on wear and corrosion properties of micro arc oxidized sic reinforced az91d magnesium alloy

    MEHMET RAGIP MUHAFFEL

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    Metalurji Mühendisliğiİstanbul Teknik Üniversitesi

    Metalurji ve Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. HÜSEYİN ÇİMENOĞLU

  2. Kedilerde distal tibia kırıklarının transartiküler hibrit eksternal fiksasyon ile sağaltımının klinik ve radyolojik değerlendirilmesi

    Clinical and radiologic evaluation of treatment of distal tibial fractures in cats with transarticular hybrid external fixation vbnmö

    MELİS GÖL

    Doktora

    Türkçe

    Türkçe

    2024

    Veteriner HekimliğiOndokuz Mayıs Üniversitesi

    Veterinerlik Cerrahisi Ana Bilim Dalı

    PROF. DR. CENK YARDIMCI

  3. A fast 3d flow field prediction around bluff bodies using deep learning

    Derin öğrenme kullanılarak küt cisimler etrafındaki 3 boyutlu akış alanının tahmini

    FARHAD NEMATI TAHER

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ABDUSSAMET SUBAŞI

  4. Futbolcularda dinamik tipte ısınma yöntemlerinin fiziksel performans üzerine akut etkisi

    The acute effects of dynamic-type warm-up methods on the physical performance among the football players

    MUHAMMED MUSTAFA AKTAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    SporSakarya Uygulamalı Bilimler Üniversitesi

    Antrenörlük Eğitimi Ana Bilim Dalı

    PROF. DR. ERTUĞRUL GELEN

  5. 2002 ve 2022 yılları arasında Ankara Üniversitesi Çocuk Onkoloji Bilim Dalı'nda tedavi edilen böbrek tümörü tanısı almış olguların retrospektif değerlendirilmesi

    Retrospective evaluation of cases diagnosed with kidney tumor treated in Ankara University Pediatric Oncology Department between 2002 and 2022

    ÇAĞLAR DOĞRUL

    Tıpta Uzmanlık

    Türkçe

    Türkçe

    2023

    Çocuk Sağlığı ve HastalıklarıAnkara Üniversitesi

    Çocuk Sağlığı ve Hastalıkları Ana Bilim Dalı

    PROF. DR. HANDAN UĞUR DİNÇASLAN