best data structure for multidimensional data?

Question

I would like to implement a simple, in-memory OLAP cube storage engine for read and write (writeback) - functionally similar to SSAS cube with multiple dimensions but one measure and only with 1 type of aggregation (sum). As in OLAP cube each axis in the multidimensional space can be a multi-level hierarchy.

Can the community provide me with some hints at which data-structures and related algorithms should I be looking at? I understand that I need something capable of indexing data in many dimensions at once, and storing intermediate precomputed aggregation values.

I'd rather not be gluing multiple nested maps together but implement something from scratch - the goal of the excercise is not just to implement this beast but also to better understand multidimensional data structures and algorithms.

Just to clarify - I am focused on the core data structure of storing multidimensional hierarchical data for reads and writes. I do not seek to implement MDX parser, make the cube persistent, etc.

Answer 1

Have a look at the list of spatial indexes at Wikipedia, one of them, like R-tree or k-d tree might be what you are looking for.