Ultra-fast influence maximization with fused sampling and sketches
Örneklem birleştirme ve veri özetleri ile yüksek performanslı etki eniyilemesi
- Tez No: 680384
- Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2015
Şehircilik ve Bölge Planlamaİstanbul Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
PROF. DR. TÜZİN BAYCAN
- 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
2024
Ulaşımİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. DİLAY ÇELEBİ GONIDIS
- 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
2008
Eczacılık ve FarmakolojiGazi ÜniversitesiFarmasötik Kimya Ana Bilim Dalı
PROF. DR. TUNCEL ÖZDEN
- Ç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
2003
Astronomi ve Uzay BilimleriEge ÜniversitesiAstronomi ve Uzay Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. GÜNAY TAŞ