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
- Tez No: 784384
- Danışmanlar: DOÇ. DR. KAMER KAYA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimi ve Mühendisliği Bilim Dalı
- Sayfa Sayısı: 73
Ö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
- Eş zamanlı konumlandırma ve haritalama tekniklerinin hız performansının geliştirilmesi
Improving runtime efficiency of simultaneous localization and mapping techniques
ZİYA UYGAR YENGİN
Yüksek Lisans
Türkçe
2017
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. VOLKAN SEZER
- İletişim ve sanat: Türk sineması dili
Communication and art: Turkish cinema language
HATİCE GÜL YALÇIN
Yüksek Lisans
Türkçe
2021
Sahne ve Görüntü SanatlarıYalova Üniversitesiİletişim ve Tasarım Ana Bilim Dalı
DOÇ. DR. SİBEL AKOVA
- Design, construction and control of an autonomous mobile rescue robot with visual feedback
Görsel geri beslemeli otonom mobil kurtarma robotunun tasarım, üretimi ve kontrol
İBRAHİM HASAN
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiGaziantep ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
Assoc. Prof. Dr. TOLGAY KARA
- Yapay sinir ağları ve destek vektör makineleri ile kemik erimesinin teşhisi
Diagnosis of osteoporosis using artificial neural networks and support vector machines
MUSTAFA İSTANBULLU
Yüksek Lisans
Türkçe
2013
Biyomühendislikİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SEDEF KENT