|
Title |
Efficient Representation of Multidimensional Data over Hierarchical Domains |
|
Authors |
Nieves Brisaboa, Ana Cerdeira-Pena, Narciso López-López, Gonzalo Navarro, Miguel Penabad, Fernando Silva-Coira |
|
Publication date |
2016 |
|
Abstract |
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 k2-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. |
|
Pages |
191-203 |
|
Conference name |
International Symposium on String Processing and Information
Retrieval |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
