Geri Dön

Ultra-fast influence maximization with fused sampling and sketches

Örneklem birleştirme ve veri özetleri ile yüksek performanslı etki eniyilemesi

  1. Tez No: 680384
  2. Yazar: GÖKHAN GÖKTÜRK
  3. Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 97

Özet

Etki Eniyileme (EE), bir sosyal ağda etkisinin bir yayılma modeline göre maksimum erişilebilirliğe ulaştığı bir düğüm alt kümesi bulma problemidir. Çözümün NP-Zorolması nedeniyle, bu problem için genellikle açgözlü yaklaşım algoritmaları uygulanır. Düzensiz bellek erişim kalıpları ve sorunun olasılıksal doğası, onu zorlu ancaködüllendirici bir optimizasyon hedefi haline getirmektedir.Bu tez, üç yüksek performanslı EE yöntemi önermekte ve gerçekleme için perfor-mans değerlendirmelerini araştırmaktadır; ilk olarak, özüt tabanlı, yön bağımsız rasgele sayı üreteci ve örneklem birleştirme kullanarak, yönlemdirilmemiş bağları örnekleyen bir EE algoritması olan InFuseR-MG'yi öneriyoruz. İkinci olarak, yönlendirilmiş ağlar için, büyük erişilebilirlik kümelerinin boyutlarımı tahmin etmekiçin değiştirilmiş Flajolet-Martin eskizleri kullanan bir EE yönetemi olan Hyper-FuseR'ı anlatacağız. Son olarak, akıllı örneklem-uzay bölümlenmesi ile birden fazla Grafik İşleme Ünitesi kullanmak için özel olarak tasarlanmış, eskiz tabanlı bir EE algoritması olan SuperFuseR önerilmiştir. Bu tezde algoritmaların her adımının performans değerlendirmeleri de tartışılmakta ve önerilen algoritmaların yüksek performanslı gerçeklemeleri de verilmektedir. Her algoritma için, literatürdeki en iyi yöntemler ile performans, kalite ve ölçeklemekarşılaştırmaları da dahil olmak üzere ayrıntılı deney sonuçları bulunmaktadır.

Özet (Çeviri)

Influence Maximization (IM) is the problem of finding a subset of vertices in a social network whose influence reaches the maximum reachability according to a diffusion model. Due to the NP-Hardness of the solution, often, greedy approximation algorithms are applied. However, irregular memory access patterns and the probabilistic nature of the problem make it a challenging yet rewarding optimization target. This thesis proposes three high-performance IM methods and explores their performance considerations for implementation; first, we propose InFuseR-MG, an IM algorithm that uses a hash-based, direction-oblivious pseudo-random number generator and fused sampling to sample edges in undirected networks. Second, we propose HyperFuseR for directed, generic networks; HyperFuseR uses modified Flajolet-Martin sketches to estimate the cardinality of large reachability sets efficiently. Finally, we propose SuperFuseR, a sketch-based IM algorithm that is specifically designed for the multi-GPU setting. SuperFuseR uses a sampling-aware sample-space split mechanism to distribute the graph to multiple devices. Also in this work, we discuss performance considerations at each step of the proposed algorithms and provide their high-performance implementations. For each algorithm, we provide detailed experimental results, including performance, quality, and scaling benchmarks

Benzer Tezler

  1. Kent yönetimi ve planlama projelerinin kurumsal kapasite, proje yönetimi ve yenilikçilik boyutları: İstanbul'da İMP deneyimi

    Urban management and institutional capacity, project management, innovation dimensions of planning projects: IMP experience from Istanbul

    ULAŞ AKIN

    Doktora

    Türkçe

    Türkçe

    2015

    Şehircilik ve Bölge Planlamaİstanbul Teknik Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    PROF. DR. TÜZİN BAYCAN

  2. Uzun mesafe taşımacılıkta elektrikli araçların Türkiye'de potansiyeli

    The potential of electric vehicles in long-distance transportation in Turkey

    LEVENT ÖZLÜ

    Doktora

    Türkçe

    Türkçe

    2024

    Ulaşımİstanbul Teknik Üniversitesi

    İşletme Mühendisliği Ana Bilim Dalı

    PROF. DR. DİLAY ÇELEBİ GONIDIS

  3. Valsartan-hidroklorotiazit içeren tabletlerde yeni miktar tayini yöntemi ve validasyonu

    The new assay method and validation of tablets which include valsartan-hydrochlorothiazide

    SANİYE BAYIR

    Yüksek Lisans

    Türkçe

    Türkçe

    2008

    Eczacılık ve FarmakolojiGazi Üniversitesi

    Farmasötik Kimya Ana Bilim Dalı

    PROF. DR. TUNCEL ÖZDEN

  4. Çok hızlı dönen tek yıldız: LO PEG

    Ultrafast rotator single star: LO PEG

    HASAN ALİ DAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2003

    Astronomi ve Uzay BilimleriEge Üniversitesi

    Astronomi ve Uzay Bilimleri Ana Bilim Dalı

    YRD. DOÇ. DR. GÜNAY TAŞ