  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.

Data Structures and Algorithms;Databases