Compact binary relation representations with rich functionality

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.

Authors

• Jérémy Barbay
• Francisco Claude
• Gonzalo Navarro

Keywords

• Binary relations
• Wavelet trees
• Compression
• Compact data structures