Compact Binary Relation Representations with Rich Functionality
Jérémy Barbay, Francisco Claude, and Gonzalo Navarro
Binary relations are an important abstraction arising in many
data representation problems.
The data structures proposed so far to represent them support just a few
basic operations required to fit one particular application.
We identify many of those operations arising in applications and generalize
them into a wide set of desirable queries for a binary relation
representation. We also identify reductions among those operations.
We then introduce several novel binary relation representations, some simple
and some quite sophisticated, that not only are space-efficient but also
efficiently support a large subset of the desired queries.