Publications

View publication

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 View PDF
Reference URL View reference page