  Binary relations are commonly used in Computer Science for modeling data. In
addition to classical representations using matrices or lists, some compressed
data structures have recently been proposed to represent binary relations in
compact space, such as the $k^2$-tree and the Binary Relation Wavelet Tree
(BRWT). Knowing their storage needs, supported operations and time performance
is key for enabling an appropriate choice of data representation given a domain
or application, its data distribution and typical operations that are computed
over the data.
  In this work, we present an empirical comparison among several compressed
representations for binary relations. We analyze their space usage and the
speed of their operations using different (synthetic and real) data
distributions. We include both neighborhood and set operations, also proposing
algorithms for set operations for the BRWT, which were not presented before in
the literature. We conclude that there is not a clear choice that outperforms
the rest, but we give some recommendations of usage of each compact
representation depending on the data distribution and types of operations
performed over the data. We also include a scalability study of the data
representations.
