Set operations over compressed binary relations

摘要

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 thek2-tree, have proven to be a competitive solution, as they are efficient in time while consuming very little space. Moreover,k2-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 usingk2-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 thek2-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.