Matrix Chain Multiplication via Multi-way Join Algorithms in MapReduce

Information

Title Matrix Chain Multiplication via Multi-way Join Algorithms in MapReduce
Authors Jaeseok Myung, Sang-goo Lee
Year 2012 / 2
Keywords Matrix Multiplication, Multi-way Join, MapReduce, Hadoop
Acknowledgement NRF
Publication Type International Conference
Publication Proceedings of the 6th International Conference on Ubiquitous Information and Communication 2012 (ICUIMC 2012)
Link url

Abstract

In this paper, we translate the multiplication of several matrices into a multi-way join operation among several relations. Matrix multiplication is widely used for many graph algorithms, such as those that calculate the transitive closure. These algorithms benefit from the multi-way join operation because this operation reduces the number of binary multiplications. Our implementation is based on the MapReduce framework, allowing us to provide scalable computation for large matrices. Although several papers have investigated matrix multiplication using MapReduce, this paper takes a different perspective. First, we expand the problem from binary multiplication to n-ary multiplication. For this reason, we apply the concept of parallelism, not only to an individual operation but also to the entire equation. Second, we represent a matrix as a relation consisting of (row, col, val) records and translate a multiplication into a join operation in database systems. This facilitates the efficient storage of sparse matrices, which are very common in real-world graph data, and the easy manipulation of matrices. Although this work is still in progress, we conducted a number of experiments to verify the idea. We also discuss current limitations and future works.