Эффективная структура данных для хранения предварительно вычисленных максимумов

Question

Рассмотрим таблицу, в которой хранятся значения двух акций переменных A и B в каждый момент времени:

         A   B
day 1   10   0 
day 2    0  10
day 3    7   7
day 4    7   7

Мы хотим ответить на такие вопросы, как:

• Какое максимальное значение было достигнуто переменной A в заданном диапазоне дней?

• Какое максимальное значение было достигнуто суммой переменных A и B в данном диапазоне дней?

Однако в реальной таблице могут быть миллиарды строк и много переменных. Чтобы получить ответы быстрее, мы планируем предварительно рассчитать сводную таблицу с меньшей детализацией по времени.

Проблема в том, что наивного вычисления максимума по новой временной гранулярности для A и B отдельно недостаточно для ответа на второй вопрос. Например:

         Max-A  Max-B
day 1&2     10     10
day 3&4      7      7

Мы утратили тот факт, что максимум A + B достигается за несколько дней 3 и 4 .

Мы можем добавить новый столбец Max- (A + B) в сводную таблицу. Но если будет много разных переменных, мы столкнемся с комбинаторным взрывом. Сводная таблица может оказаться больше оригинальной!

Существует ли алгоритм / структура данных для эффективного хранения предварительно вычисленных максимумов такого типа, чтобы мы могли задавать вопросы о произвольных комбинациях переменных, избегая при этом комбинаторного взрыва? Я предполагаю, что он может предположить некоторые закономерности в данных и попытаться использовать их - ценой некоторой общности.

Answer 1

Не существует действительно хорошей структуры данных для всего, что вы хотите ... но вы знаете, что в году всего 365 дней, т. Е. В вашей таблице не будет миллиардов строк.

Таблица будет содержать не более нескольких тысяч строк, поэтому не потребуется значительного количества времени, чтобы просто выполнить итерацию по ней и вычислить любую статистику, которая вам нравится.