Приближение гистограммы для потоковой передачи данных

Этот вопрос является небольшим расширением того, на который дан ответ здесь ]. Я работаю над повторной реализацией версии аппроксимации гистограммы, приведенной в разделе 2.1 этой статьи , и я хотел бы собрать всех своих уток подряд, прежде чем снова начать этот процесс. В прошлый раз я использовал boost :: multi_index , но производительность была не самой высокой, и я хотел бы избежать логарифмической сложности вставки / поиска в сегментах std :: set . Из-за количества гистограмм, которые я использую (по одной на объект для каждого класса на листовой узел случайного дерева в случайном лесу), вычислительная сложность должна быть как можно более близкой к постоянной.

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

1. инициализировать стандартный массив C размера N, где N = количество ячеек; и
2. умножьте входное значение (действительное число) на некоторый коэффициент и уменьшите результат, чтобы получить его индекс в массиве C.

Это хорошо работает для гистограмм с одинаковым размером ячейки и довольно эффективно. Однако в разделе 2.1 упомянутой выше статьи представлен алгоритм гистограммы без единых размеров ячеек.

Еще одна проблема заключается в том, что простое умножение введенного действительного значения на коэффициент и использование полученного продукта в качестве индекса приводит к ошибке с отрицательными числами. Чтобы решить эту проблему, я подумал о том, чтобы определить ячейку «0» где-нибудь в массиве. Этот лоток будет центрирован на 0,0; бункеры выше / ниже могут быть рассчитаны с использованием того же метода умножения и пола, который был только что объяснен, с небольшой модификацией, заключающейся в том, что продукт с напольным покрытием добавляется к двум или вычитается из двух по мере необходимости.

Тогда возникает вопрос о слиянии: алгоритм, описанный в статье, объединяет два ближайших интервала, измеряемых от центра к центру. На практике это создает аппроксимацию «зубчатой» гистограммы, потому что некоторые интервалы будут иметь очень большие счетчики, а другие - нет. Конечно, это происходит из-за бинов неоднородного размера и не приводит к потере точности. Однако потеря точности происходит, если мы пытаемся нормализовать бункеры неоднородного размера, чтобы сделать единообразными. Это из-за предположения, что m / 2 выборки попадают слева и справа от центра бина, где m = количество бинов.Мы могли бы смоделировать каждую ячейку как гауссову, но это все равно приведет к потере точности (хотя и минимальной)

Вот где я сейчас застрял, что приводит к следующему важному вопросу: Какой лучший способ реализовать гистограмму, принимающую потоковые данные и сохраняющую каждую выборку в ячейках одинакового размера?