###
Compact Data Structures Meet Databases

####
Gonzalo Navarro

We describe two success stories on the application of compact data structures
(cds) to solve the problem of the excessively redundant space requirements
posed by worst-case-optimal (wco) algorithms for multijoins in databases, and
particularly basic graph patterns on graph databases. The aim of cds is to
represent the data {\em and} additional data structures on it, using total
space close to that of the plain (and, sometimes, compressed) data, while
efficiently simulating the data structure operations. Cds turn out to be a
perfect approach for the described problem: We designed and implemented cds that
effectively use space close to that of the plain or compressed data, which is
orders of magnitude less than existing systems, while retaining worst-case
optimality and performing competitively with those
systems in query time, sometimes being even considerably faster.