|
Title |
Worst-Case Optimal Graph Joins in Almost No Space |
|
Authors |
Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan Reutter, Adrián Soto |
|
Publication date |
2021 |
|
Abstract |
We present an indexing scheme that supports worst-case optimal (wco) joins over graphs within compact space. Supporting all possible wco joins using conventional data structures - based on B(+)-Trees, tries, etc. - requires 6 index orders in the case of graphs represented as triples. We rather propose a form of index, which we call a ring, that indexes each triple as a set of cyclic bidirectional strings of length 3. Rather than maintaining 6 orderings, we can use one ring to index them all. This ring replaces the graph and uses only sublinear extra space on top of the graph; in order words, the ring supports worst-case optimal graph joins in almost no space beyond storing the graph itself. We perform experiments using our representation to index a large graph (Wikidata) in memory, over which wco join algorithms are implemented. Our experiments show that the ring offers the best overall performance for query times while using only a small fraction of the space when compared with several state-of-the-art approaches. |
|
Pages |
102-114 |
|
Conference name |
SIGMOD International Conference on Management of Data |
|
Publisher |
ACM Press (New York, NY, USA) |
|
Reference URL |
|
