RBForest: Efficient In-Memory Format for Sparse Matrices on Dynamic Workloads

Abstract

Sparse matrices only store nonzero entries with their positional information. Thus, while dense matrices typically store all of their entries in a one-dimensional array, sparse matrices have various choices of internal data structures to use. So there can be many different in-memory formats where sparse matrices are managed. Various sparse matrix formats have been proposed, and they have advantages in different ways. Formats that support fast linear algebra operations cannot handle matrix updates quickly and vice versa. However, several use cases of sparse matrices are highly dynamic. So the sparse matrices are expected to periodically process analytic queries, including linear algebra operations, while quickly handling a stream of matrix updates. Thus, one of the mainstream strategies is to manage a sparse matrix in an update-friendly format during matrix updates and convert it to a format for fast linear algebra operations when we need to process analytic queries. To make the best use of this strategy, this paper proposes a new sparse matrix format called RBForest. The RBForest manages one red-black tree per row to reduce the tree re-balancing cost after the insertion or deletion of nonzero entries. It also manages a hash table to enable immediate access to its nonzero elements, reducing the initial search cost for all types of matrix updates. Our evaluations show that the RBForest performs more efficiently on real dynamic workloads than previously proposed formats that adhere to the same strategy.