Алгоритм DWARF
Алгоритм DWARF (карлик) (см. [21]) назван так с намеком на звезды карликового типа, которые имеют небольшой объем, но огромную массу. Это синтаксический алгоритм, распознающий два типа избыточности хранения данных и устраняющий их во время создания и поддержки куба.
Ключевыми понятиями алгоритма являются префиксная избыточность и суффиксная избыточность (см. ).
В пользу практического использования алгоритма DWARF говорит автоматическое нахождение префиксных и суффиксных избыточностей, не требующее каких-либо знаний о распределении данных, типов, значений. При этом эффективность сжатия одинаково высока как и для ''разреженных'', так и для ''плотных'' кубов. В большинстве случаев даже для очень плотных кубов размер результирующего DWARF куба меньше размера базовой таблицы. Если для ''плотных'' кубов улучшения происходят за счет префиксной избыточности, то, по мере того как кубы становятся ''разреженнее'', возрастает доля суффиксной избыточности.
Не менее важным является сокращение времени создания и расчетов. Каждый избыточный суффикс идентифицируется до его вычисления, что ведет к существенным уменьшениям времени создания. Более того, вследствие уменьшения общего размера куба пропорционально падает и время обработки запросов.
