Brisaboa, Nieves R.Cerdeira-Pena, AnaLópez-López, NarcisoNavarro, GonzaloPenabad, Miguel R.Silva-Coira, Fernando2017-02-232017-02-232016-09-21Brisaboa N.R., Cerdeira-Pena A., López-López N., Navarro G., Penabad M.R., Silva-Coira F. (2016) Efficient Representation of Multidimensional Data over Hierarchical Domains. In: Inenaga S., Sadakane K., Sakai T. (eds) String Processing and Information Retrieval. SPIRE 2016. Lecture Notes in Computer Science, vol 9954. Springer, Cham0302-97431611-3349http://hdl.handle.net/2183/18175The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_19[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 k2k2 -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.engEfficient representationMultidimensional dataHierarchical domainsOLAP databasesconference outputopen access10.1007/978-3-319-46049-9_19