Compressed Dynamic Binary Relations

We introduce a dynamic data structure for the compact representation of binary relations R ⊆ A × B. Apart from checking whether two objects (a, b) ∈ A × B are related, and listing the objects of B related to some a ∈ A and vice versa, the structure allows inserting and deleting pairs (a, b) in the relation, as well as modifying the base sets A and B. The data structure is a dynamic variant of the k²-tree, a static compact representation that takes advantage of clustering in the binary relation to achieve compression. We apply our dynamic data structure to the representation of Web graphs and RDF databases, showing that it combines good compression ratios with fast query and update times.