Классика баз данных - статьи
Аппроксимация значений внутри каждого бакета
При заданном объеме пространства под гистограмму одним из основных компромиссов является сочетание числа бакетов и объема информации, сохраняемой в каждом бакете. Малый объем информации внутри каждого бакета влечет грубые локальные аппроксимации и большее число бакетов. Ключевым вопросом является нахождение правильного баланса в этом компромиссе для оптимизации общей аппроксимации распределения данных.
По отношению к аппроксимации множества значений, попадающих в одномерный бакет, имеются два подхода. При традиционном предположении о непрерывности значений поддерживается наименьший объем информации (только минимальное и максимальное значения), но ничего такого, что могло бы каким-то образом подсказать, сколько значений имеется, и какими они могли бы быть. При использовании более современного предположения о равномерности промежутков [] также поддерживается число значений внутри каждого бакета, и реальное множество значений аппроксимируется множеством, формируемым путем (виртуального) размещения того же числа значений на равных расстояниях между минимальным и максимальным значениями. В другом варианте этого подхода предлагается сохранять не реальную среднюю протяженность внутри бакета, а протяженность, которая сокращает уровень ошибки общей аппроксимации при запросах по диапазонам значений, принимая во внимание распространенность конкретных диапазонов внутри каждого бакета []. Имеется несколько исследований, показывающих превосходство каждого из общих методов над другим; это свидетельствует о том, что абсолютного победителя может и не существовать.
Два упомянутых основных подхода расширены и на случай многомерных бакетов с поддержкой в бакете минимального и максимального значений каждого измерения. При использовании предположения о непрерывности значений больше ничего и не требуется, но при использовании предположения о равномерности промежутков возникает проблема: существование каких (многомерных) значений предполагается в бакете? Если di - это число различных значений в атрибуте Xi , присутствующих в бакете, и vi '(k) - k-ое приближенное число в измерении i (полученное путем применения предположения о равномерности протяженности по этому измерению), то разумно предположить, что в бакете присутствуют все возможные комбинации <v1'(k1), …, vn '(kn )>, 1 ≤ ki ≤ di [].
В одной интересной исследовательской работе в мир одномерных гистограмм было введено использование стержневой оценки (kernel estimation) [] специально для работы с вещественными данными. Грубо говоря, в этом методе предлагается выбирать точки существенного изменения функции плотности вероятности в качестве границ бакетов (в духе, напоминающем ограничение разделения maxdiff), а затем применять традиционный метод стержневой оценки для аппроксимирования значений внутри каждого бакета. Это также обобщено на многомерный случай [].
