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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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