Performance evaluation of space efficient graph algorithms

Abstract

Various graphs from social networks or big data may contain gigantic data. Searching such graph requires memory scaling with graph. Asano et al. ISAAC (2014) initiated the study of space efficient graph algorithms, and proposed algorithms for DFS and some applications using sub-linear space which take slightly more than linear time. Banerjee et al. ToCS 62(8), 1736-1762 (2018) proposed space efficient graph algorithms based on read-only memory(ROM) model. Given a graph G with n vertices and m edges, their BFS algorithm spends O(m + n) time using 2n + o(n) bits. The space usage is further improved to nlg3 + o(n) bits with O(mlgn f(n)) time, where f(n) is extremely slow growing function of n. For DFS, their algorithm takes O(m + n) time using O(mlg(m/n)). Chakraborty et al. ESA (2018) introduced in-place model. The notion of in-place model is to relax the read-only restriction of ROM model to improve the space usage of ROM model. Algorithms based on in-place model improve space usage exponentially, to O(lgn) bits, at the expense of slower runtime. In this thesis, we focus on exploring proposed space efficient graph algorithms of ROM model and in-place model in detail and evaluate performance of those algorithms. We implemented almost all the best-known space-efficient algorithms for BFS and DFS, and evaluated their performance. Along the way, we also implemented several space-efficient data structures for representing bit vectors, strings, dictionaries etc.

소셜 네트워크나 빅 데이터로부터 생성된 다양한 그래프들은 방대한 양의 데이터를 포함하고 있다. 이러한 그래프를 탐색하기 위해서는 그래프의 크기에 비례하여 필요한 메모리의 용량이 늘어난다. Asano 등(ISAAC (2014))은 공간 효율적 그래프 알고리즘 연구를 개시했다. 이 연구를 통해 선형적 시간보다 약간 더 걸리는 대신 저선형적 공간을 사용하는 DFS 알고리즘과 활용 방안들이 제안됐다. Banerjee 등(ToCS 62(8), 1736-1762 (2018))은 ROM 모델을 기반으로 하는 공간 효율적인 그래프 알고리즘들을 제안했다. 그래프 G의 n개의 정점과 m개의 간선이 주어졌을 때, O(m + n)의 시간과 2n + o(n) 의 비트를 사용하는 BFS가 제안됐고, f(n)을 n에 비례해서 매우 느리게 커지는 함수라고 했을 때, O(mlgnf(n))의 시간과 nlg3 + o(n)의 비트를 사용하는 알고리즘이 제안됐다. DFS의 경우, O(m + n)의 시간과 O(mlg m n )의 비트를 사용하는 알고리즘이 제안됐다. Chakraborty 등(ESA (2018))은 ROM 모델이 가지고 있는 한계점을 넘기 위해 ROM 모델의 제한점을 완화시키는 in-place 모델을 소개했다. In-place 모델을 기반으로 한 알고리즘들은 n + O(lgn)의 비트를 사용하여 BFS와 DFS를 수행할 수 있고, 추가적으로 더 긴 시간을 소요하여 O(lgn) 비트의 공간만으로 알고리즘을 수행할 수 있다. 이 논문에서는 ROM 모델과 in-place 모델에서 제안된 다양한 알고리즘들을 연구 및 구현하고 실험을 통하여 이들 알고리즘의 수행 결과를 평가한다.