Compressed representation of dynamic binary relations with applications

Abstract

We introduce a dynamic data structure for the compact representation of binary relations R subset of A x B. The data structure is a dynamic variant of the k(2)-tree, a static compact representation that takes advantage of clustering in the binary relation to achieve compression. Our structure can efficiently check whether two objects (a, b) is an element of A x B are related, and list the objects of B related to some a is an element of A and vice versa. Additionally, our structure allows inserting and deleting pairs (a, b) in the relation, as well as modifying the base sets A and B. We test our dynamic data structure in different contexts, including the representation of Web graphs and RDF databases. Our experiments show that out dynamic data structure achieves good compression ratios and fast query times, close to those of a static representation, while also providing efficient support for updates in the represented binary relation.