Efficient Representation of Multidimensional Data over Hierarchical Domains
Nieves Brisaboa, Ana Cerdeira-Pena, Narciso López-López,
Gonzalo Navarro, Miguel Penabad, and Fernando Silva-Coira
We consider the problem of representing multidimensional data where the
domain of each dimension is organized hierarchically,
and the queries require summary information at a different node in the
hierarchy of each dimension. This is the typical case of OLAP databases.
A basic approach is to represent each hierarchy
as a one-dimensional line and recast the queries as multidimensional range
queries. This approach can be implemented compactly by generalizing to more
dimensions the k^2-treap, a compact representation of
two-dimensional points that allows for efficient summarization queries along
generic ranges. Instead, we propose a more flexible generalization, which
instead of a generic quadtree-like partition of the space, follows the
domain hierarchies across each dimension to organize the partitioning. The
resulting structure is much more efficient than a generic multidimensional
structure, since queries are resolved by aggregating much fewer nodes of the
tree.