|
Title |
Boosting Graph Joins and Matrix Multiplications in Little Space |
|
Authors |
Diego Arroyuelo, José Cazorla, Gonzalo Navarro |
|
Publication date |
2026 |
|
Abstract |
Qdags are extremely succinct representations of relations that have been used to implement worst-case-optimal joins in graph databases, as well as regular path queries and sparse matrix multiplications. While they are very fast on joins over few attributes, their performance sharply degrades over more attributes. In this paper we introduce a so-called prejoining technique that builds joins over fewer attributes and adds their outputs as new tables in the main join. We show that prejoining boosts qdags by orders of magnitude, letting them outperform a number of representative systems over a range of join shapes and on real Wikidata queries. Applied to sparse Boolean matrix multiplication, prejoining boils down to a compressed implementation of the well-known Shoor's algorithm, which we show to sharply outperform classic recursive multiplication, the only one implemented so far on little space. |
|
Pages |
article 7 |
|
Conference name |
ACM SIGMOD Joint International Workshop on Graph Data
Management
Experiences & Systems (GRADES) and Network Data Analytics (NDA) |
|
Publisher |
ACM Press (New York, NY, USA) |
|
Reference URL |
|
