###
Compressed Dynamic Binary Relations

####
Nieves Brisaboa, Guillermo de Bernardo, and Gonzalo Navarro

We introduce a dynamic data structure for the compact representation of binary
relations *R subset A x B*. Apart from checking whether
two objects *(a,b) in A x B* are related, and listing the objects of
*B*
related to some *a in 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^2-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.