Обзор алгоритмов MOLAP

Многопозиционное агрегирование массивов для вычисления кубов


Многопозиционное агрегирование (MultiWay Array Aggregation, далее MultiWay, см. [27]) рассчитывает полный куб, используя в качестве базовой структуры данных многомерный массив. Это типичный MOLAP-подход, в котором применяется прямая адресация ячеек многомерного массива, и для обращения к элементам измерений используются их индексы или позиции в массиве. Поэтому MultiWay не может использовать ни одну из техник, связанных с переупорядочиванием ячеек в зависимости от значений мер. Укрупненно алгоритм выглядит следующим образом:

  • Разбиение массива на блоки (chunks). Блоками называются подкубы достаточно малого размера, которые можно разместить в оперативной памяти, выделенной для расчета куба. Разбиение на блоки (chunking) — метод разделения n-мерного массива на меньшие n-мерные блоки, каждый из которых хранится в виде объекта на жестком диске. Блоки сжимаются, чтобы избежать хранения пустых ячеек (см. раздел ). К примеру, ссылки вида (СсылкаНаБлок + СмещениеВнутриБлока) могут быть использованы в качестве механизма адресации ячеек, что позволяет сжимать разреженные массивы и осуществлять быстрый поиск ячеек внутри блока. Подобный подход достаточно эффективен при работе с разреженным кубами как в оперативной памяти, так и на диске.
  • Вычисление агрегатов при обращении к ячейкам куба. Агрегированные показатели в ячейках вычисляются только в момент обращения к этим ячейкам, поэтому важен порядок обхода ячеек куба. Необходимо минимизировать количество обращений к одной и той же ячейке, поскольку это сократит объем необходимой оперативной памяти и места на жестком диске. Сложность заключается в подборе порядка таким образом, чтобы частичные агрегаты вычислялись одновременно для нескольких подкубов.

    Поскольку в таком подходе данные для вычисления агрегатов часто пересекаются, он называется многопозиционным. Агрегирование происходит одновременно по многим измерениям для уменьшение расходов на чтение данных в оперативную память.

    Рассмотрим конкретный пример вычисления куба этим методом.



    Содержание раздела