arXiv preprint ·
Compressed Boolean Matrix Multiplication using Bicliques
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Boolean matrix multiplication is a fundamental operation in many graph-based applications, including web and social network analysis, information retrieval, and graph query evaluation. However, conventional sparse representations such as CSR}/CSC still incur significant space and time costs on large graphs. In this work, we introduce a method for multiplying Boolean matrices based on a biclique-based compressed representation that decomposes them into dense bipartite subgraphs, thereby capturing large sets of implicit edges. We first improve the iterative biclique extraction algorithm of Hernández and Navarro by introducing percentile-based parameter adaptation that dynamically adjusts its parameters according to the degree distribution, enhancing both extraction efficiency and compression ratio. We then extend the Schoor multiplication algorithm to operate directly on biclique-encoded matrices, thereby enabling a compositional form of multiplication where the output can also be represented as a collection of bicliques. Our experimental results on large real-world web and social graphs show that our approach achieves substantial reductions in space and computation time with respect to CSR/CSC-based representations. For example, using biclique extraction just as a tool to speed up multiplication (but retaining the CSR/CSC format) yields up to 34-fold speedups. Further, using the biclique-based representation for input and output yields up to a 10-fold reduction in space and up to a 290-fold speedup for matrix multiplication. These results demonstrate that our representation based on bicliques is both space- and time-effective to support an algebra of Boolean matrices.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Beyond 3SUM-Hardness for Geometric Problems
Approximation algorithms for identical parallel machine scheduling with assignment costs
The Exact Robustness of Smith's Rule with Predicted Processing Times
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Exact Algorithms and Complexity of the Smallest Grammar Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.