Abstract We introduce a dynamic data structure for the compact representation of binary relations ℛ ⊆ × . Apart from checking whether two objects ( , ) ∈ × are related, and listing the objects of related to some ∈ and vice versa, the structure allows inserting and deleting pairs ( , ) in the relation, as well as modifying the base sets and . 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.
A dynamic variant of the K 2 -tree that combines good compression ratios with fast query and update times has been proposed REF .
Compressed Dynamic Binary Relations
2012 Data Compression Conference
2012 Data Compression Conference
Computer Science