Bitwise Algorithms to Compute the Transitive Closure of Graphs in Python.

The transitive closure (TC) of a graph is a core problem in graph analytics. There exist many High Performance Computing (HPC) and database solutions to solve the TC problem for “big graphs”. However, they generally require the graph to fit in main memory and they require converting into specific binary file formats. To solve such limitations, this paper presents a novel solution to solve TC within the Python library ecosystem, combining HPC techniques and database system algorithms. We introduce two complementary algorithms removing HPC memory limitations: (1) an algorithm that efficiently converts edges into bit vectors and (2) a database-oriented, bit-vector, highly parallel matrix algorithm, which processes the graph in blocks. An experimental evaluation shows our solution provides better performance than state-of-the-art Python libraries.