Generating landmark labels for short distance queries in a distributed setting

Official URL: https://risc01.sabanciuniv.edu/record=b2862147_(Table of contents)

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.