Compact Rich-Functional Binary Relation Representations
Jérémy Barbay, Francisco Claude, and Gonzalo Navarro
Binary relations are an important abstraction arising in a number of
data representation problems.
Each existing data structure specializes in the few basic operations
required by one single application, and takes only limited advantage
of the inherent redundancy of binary relations.
We show how to support more general operations efficiently, while
taking better advantage of some forms of redundancy in practical
instances.
As a basis for a more general discussion on binary relation data
structures, we list the operations of potential interest for
practical applications, and give reductions between operations.
We identify a set of operations that yield the support of all
others.
As a first contribution to the discussion, we present two
data structures for binary relations, each of which achieves a
distinct tradeoff between the space used to store and index the
relation, the set of operations supported in sublinear time, and the
time in which those operations are supported.
The experimental performance of our data structures shows that they
not only offer good time complexities to carry out many
operations, but also take advantage of regularities that arise in practical
instances in order to reduce space usage.