Generating landmark labels for short distance queries in a distributed setting

Şener, Arda (2022) Generating landmark labels for short distance queries in a distributed setting. [Thesis]

[thumbnail of 10395489.pdf] PDF

Download (2MB)


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.
Item Type: Thesis
Uncontrolled Keywords: Graphs. -- High-Performance Computing. -- Parallel Algorithms. -- Distance Queries. -- Çizgeler. -- Yüksek Başarımlı Hesaplama. -- Paralel Algoritmalar. -- Uzaklık Sorguları.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Dila Günay
Date Deposited: 10 Jul 2023 11:09
Last Modified: 10 Jul 2023 11:09

Actions (login required)

View Item
View Item