Efficient Representation of Multidimensional Data over Hierarchical Domains

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 represe...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-12
Main Authors: Brisaboa, Nieves R, Cerdeira-Pena, Ana, López-López, Narciso, Navarro, Gonzalo, Penabad, Miguel R, Silva-Coira, Fernando
Format: Article
Language:English
Subjects:
Domains
Hierarchies
Multidimensional data
Online analytical processing
Queries
Representations
Servers
Software reviews
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1612.04094