Set operations over compressed binary relations

Abstract

[Abstract]: Binary relations are commonly used to represent relationships between real-world objects. Classical representations for binary relations can be very space-consuming when the set of elements is large. In these cases, compressed representations, such as the -tree, have proven to be a competitive solution, as they are efficient in time while consuming very little space. Moreover, -trees can successfully represent both sparse and dense binary relations, using different variants of the technique. In this paper, we propose and evaluate algorithms to efficiently perform set operations over binary relations represented using -trees. More specifically, we present algorithms for computing the union, intersection, difference, symmetric difference, and complement of binary relations. Thus, this work extends the functionality of the different variants of the -tree representation for binary relations. Our algorithms are computed directly over the compressed representation, without requiring previous decompression, and generate the result in compressed form. The experimental evaluation shows that they are efficient in terms of space and time, compared with different baselines where the binary relations are represented in plain form or require a previous decompression to perform the set operation.