Geri Dön

Generating landmark labels for short distance queries in a distributed setting

Dağıtık ortamda en kısa yol sorguları için yer işareti etiketleri oluşturma

PDF İndir

  1. Tez No: 784384
  2. Yazar: ARDA ŞENER
  3. Danışmanlar: DOÇ. DR. KAMER KAYA
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Mathematics, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Grafikler, Paralel algoritmalar, Paralel hesaplama, Yüksek başarımlı hesaplama, Graphics, Parallel algorithms, Parallel computing, High performance computing
  7. Yıl: 2022
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimi ve Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Uzaklık sorguları ağ analiz işlemlerinin önemli ve temel bir parçasıdır. Bu sorgular sosyal ağlarda kullanıcıların yakınlığının öğrenilmesi, internet üzerinde sitelerin ilişkilerinin karşılaştırılması, biyolojik ağlarda moleküllerin birbiriyle etkileşimlerinin incelenmesi gibi alanlarda kullanılabilir. Dolayısıyla, bu sorguların hızlı bir şekilde cevaplanabilmesi ağ analizi alanına genel olarak yarar sağlamaktadır. PLL (Pruned Landmark Labeling) adı verilen algoritma, bu sorguların çok daha kısa sürede cevaplanabilmesini sağlayan yer işaretleri oluşturmak için literatürde sıklıkla kullanılmaktadır. PSL (Parallel Shortest-distance Labeling) algoritması PLL tabanlı paralel hesaplama yapılabilen ortamlarda kullanılmak üzere tasarlanmış ve özellikle sosyal ağlarda kullanılan bir algoritmadır. Fakat PLL tabanlı algoritmaların hafıza karmaşıklığı oldukça fazladır. Örneğin, orta boyutlu çizgeler için bile oluşturulan yer işaretleri hafızada 300GB üzerinde yer kaplayabilmektedir. Bununla beraber, orta boyutlu çizgelerde, modern bir CPU çekirdeği ile yer işaretlerini oluşturmak için 12 günden uzun süre harcayabilmektedir. Bu tez PSL algoritmasının dağıtık bir ortamda uygulanmasının çizgenin bölünmesi ve dağıtılması aracılığı ile uygulanması üzerinedir. Bu teknik ile hem zaman, hem kullanılan hafıza açısından önemli kazanımlar sağlanmıştır. Ek olarak, bu tez, PSL algoritmasının performansının artırılmasına yönelik deney ve teknikler de içermektedir.

Özet (Çeviri)

Distance queries are a fundamental part of many network analysis applications. Distances can be used to infer the closeness of two users in social networks, the relation between two websites in a web graph, or the importance of the interaction between two proteins or molecules. As a result, being able to answer these queries rapidly has many benefits to the area of network analysis as a whole. Pruned landmark labeling is a technique used to generate an index for a given graph that allows the shortest path queries to be completed in a fraction of the time when compared to a standard BFS (Breadth First Search) based algorithm. PSL (Parallel Shortest-distance Labeling) is a pruned landmark labeling algorithm that is designed to be implemented in a multithreaded environment and works particularly well on social networks. Unfortunately, even for a medium-size, 50 million vertex graph, the index size can be as large as 300GB. On the same graph, a single CPU core takes more than 12 days to generate the index. This thesis aims to implement PSL in a distributed environment by partitioning the input graph and distributing the partitions to the nodes. Our method can provide improvements in both the execution time and the memory consumption by distributing both across multiple nodes of a cluster. Furthermore, we develop techniques and conduct experiments that can help increase the performance of the PSL algorithm.

Benzer Tezler

  1. Tez No

    31

    Realization of transmitter and receiver clock generation units and channel switching unit in a modified analog radio relay

    Değiştirilen bir analog radyodaki verici ve alıcı saat üretimi birimleri ve kanal anahtarlama biriminin gerçekleştirilmesi

    AYHAN BÜYÜKSEMERCİ

    Yüksek Lisans

    İngilizce

    İngilizce

    1987

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MURAT AŞKAR

  2. Tez No

    33

    New algorithms and techniques for microprocessor-controlled PWM induction drives

    Başlık çevirisi yok

    OSMAN KÜKRER

    Doktora

    İngilizce

    İngilizce

    1987

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. H. BÜLENT ERTAN

  3. Tez No

    232

    Barajların hacim-verim ilişkisi üzerine bir araştırma

    Başlık çevirisi yok

    MEHMET KILIÇARSLAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1987

    İnşaat MühendisliğiÇukurova Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TEFARUK HAKTANIR

  4. Tez No

    356

    Akaryakıtla çalışan endüstriyel tav fırınlarında yanma, sıcaklık ve basıncın optimum kontrolu

    Optimum control of combustion temperature and pressure in industrial tempering furnaces working with fuel-oil

    MEHMET EROĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    1987

    Makine MühendisliğiGazi Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. YÜCEL ERCAN

  5. Tez No

    299

    Bornova ekolojik koşullarında bazı haşhaş çeşitlerinin verim ve kaliteleri üzerinde araştırmalar

    The Investigations on the yield and qualities of some popy vasied Bornova ecological conditions

    HAMDİ AYGÜN

    Yüksek Lisans

    Türkçe

    Türkçe

    1985

    ZiraatEge Üniversitesi

    Tarla Bitkileri Ana Bilim Dalı

    PROF. DR. ŞÜKRÜ HAZIM EMİROĞLU

Geri Dön