meilleure structure de données pour les données multidimensionnelles?

Question

Je voudrais implémenter un simple moteur de stockage de cube OLAP en mémoire pour lecture et écriture (écriture différée) - fonctionnellement similaire au cube SSAS avec plusieurs dimensions mais une mesure et seulement avec 1 type d'agrégation (somme). Comme dans le cube OLAP, chaque axe de l'espace multidimensionnel peut être une hiérarchie à plusieurs niveaux. Est-ce que la communauté peut me fournir quelques indications sur les structures de données et les algorithmes associés que je devrais regarder? Je comprends que j'ai besoin de quelque chose capable d'indexer des données dans plusieurs dimensions à la fois, et de stocker des valeurs d'agrégation précalculées intermédiaires. Je préférerais ne pas coller plusieurs cartes imbriquées ensemble mais implémenter quelque chose à partir de zéro - le but de l'exercice n'est pas seulement d'implémenter cette bête mais aussi de mieux comprendre les structures de données multidimensionnelles et les algorithmes. Juste pour clarifier - Je me concentre sur la structure de données de base de stockage des données hiérarchiques multidimensionnelles pour les lectures et les écritures. Je ne cherche pas à mettre en œuvre l'analyseur MDX, faire le cube persistant, etc.

Answer 1

Jetez un oeil à the list of spatial indexes at Wikipedia, l'un d'entre eux, comme R-tree ou k-d tree peut-être ce que vous recherchez.