Амортизировать расчет распределения (и процентили), применимый в App Engine?

Question

Это применимо к Google App Engine, но не обязательно ограничено для него.

В Google App Engine база данных не реляционная, поэтому никакие агрегатные функции (такие как сумма, среднее и т. Д.) Не могут быть реализованы. Каждый ряд не зависит друг от друга. Чтобы вычислить сумму и среднее значение, приложение просто должно амортизировать свои расчеты путем пересчета для каждой отдельной новой записи в базу данных, чтобы она всегда была актуальной.

Как можно было бы рассчитать процентиль и распределение частот (то есть плотность)? Я хотел бы сделать график плотности поля значений, и этот набор значений, вероятно, порядка миллионов. Может быть целесообразно выполнить цикл по всему набору данных (предел для каждого запроса составляет 1000 возвращаемых строк) и рассчитать на основе этого, но я бы предпочел сделать некоторый разумный подход.

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

Кстати, данные неопределенны, так как максимум и минимум могут быть повсюду. Таким образом, распределение должно занимать примерно 95% данных и делать только плотность, основанную на этом.

Answer 1

Получение всей строки (с этим пределом 1000 за раз ...) снова и снова, чтобы получить одно число на строку, безусловно, непривлекательно. Поэтому денормализуйте данные, записав это единственное число в отдельном объекте, который содержит список чисел (я полагаю, до 1 МБ на запрос, поэтому с 4-байтовыми числами не более 250 000 номеров в списке).

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

Если данные для элемента могут быть изменены, есть отдельные объекты одного и того же вида, записывающие «удаленные» значения данных; чтобы изменить значение одного элемента с 23 на 45, добавьте 23 к последнему списку «удаленных значений» и 45 к последнему «добавленным значениям» - это также относится и к удалению элемента.

Answer 2

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

Это самый очевидный подход ко мне, почему вы пытаетесь избежать этого?