|
Title |
Compact Binary Relation Representations with Rich Functionality |
|
Authors |
Jérémy Barbay, Francisco Claude, Gonzalo Navarro |
|
Publication date |
2013 |
|
Abstract |
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. |
|
Downloaded |
7 times |
|
Pages |
19-37 |
|
Volume |
232 |
|
Journal name |
Information and Computation |
|
Publisher |
Elsevier Science (Amsterdam, The Netherlands) |
|
PDF |
|
|
Reference URL |
|
