Гистограммы чаще всего используются в качестве визуального представления данных. Однако системы баз данных используют гистограммы для внутреннего суммирования данных и предоставления оценок размера для запросов . Эти гистограммы не представляются пользователям и не отображаются визуально, поэтому для их построения доступен более широкий диапазон опций. Простые или экзотические гистограммы определяются четырьмя параметрами: значением сортировки, исходным значением, классом раздела и правилом раздела. Самая простая гистограмма — это гистограмма равной ширины, где каждый блок представляет один и тот же диапазон значений. Такая гистограмма будет определена как имеющая значение сортировки значения, исходное значение частоты, находящаяся в классе последовательного раздела и имеющая правило раздела, утверждающее, что все блоки имеют один и тот же диапазон.
V-оптимальные гистограммы являются примером более «экзотической» гистограммы. V-оптимальность — это правило разбиения, которое гласит, что границы блоков должны быть размещены так, чтобы минимизировать кумулятивную взвешенную дисперсию блоков. Реализация этого правила — сложная проблема, и построение этих гистограмм — также сложный процесс.
V-оптимальная гистограмма основана на концепции минимизации величины, которая в данном контексте называется взвешенной дисперсией . [1] Она определяется как
где гистограмма состоит из J ячеек или контейнеров, n j — количество элементов, содержащихся в j- й ячейке, а V j — дисперсия между значениями, связанными с элементами в j -й ячейке.
Следующий пример построит V-оптимальную гистограмму, имеющую значение сортировки Value, исходное значение Frequency и класс разбиения Serial. На практике почти все гистограммы, используемые в исследовательских или коммерческих продуктах, относятся к классу Serial, что означает, что последовательные значения сортировки помещаются либо в один и тот же блок, либо в последовательные блоки. Например, значения 1, 2, 3 и 4 будут в блоках 1 и 2 или блоках 1, 2 и 3, но никогда в блоках 1 и 3. Это будет принято как предположение в любом дальнейшем обсуждении.
Возьмем простой набор данных, например, список целых чисел:
1, 3, 4, 7, 2, 8, 3, 6, 3, 6, 8, 2, 1, 6, 3, 5, 3, 4, 7, 2, 6, 7, 2
Вычислить пары значений и частот (1, 2), (2, 4), (3, 5), (4, 2), (5, 1), (6, 4), (7, 3), (8, 2)
Наша V-оптимальная гистограмма будет иметь два блока. Поскольку один блок должен заканчиваться в точке данных для 8, мы должны решить, где разместить границу другого блока. Правило V-оптимальности гласит, что кумулятивная взвешенная дисперсия блоков должна быть минимизирована. Мы рассмотрим два варианта и вычислим кумулятивную дисперсию этих вариантов.
Вариант 1: Корзина 1 содержит значения от 1 до 4. Корзина 2 содержит значения от 5 до 8.
Ковш 1:
Средняя частота 3,25
Взвешенная дисперсия 2,28
Ковш 2:
Средняя частота 2,5
Взвешенная дисперсия 2,19
Сумма взвешенной дисперсии 4,47
Вариант 2: Корзина 1 содержит значения от 1 до 2. Корзина 2 содержит значения от 3 до 8.
Ковш 1:
Средняя частота 3
Взвешенная дисперсия 1,41
Ковш 2:
Средняя частота 2,83
Взвешенная дисперсия 3,29
Сумма взвешенной дисперсии 4,70
Первый вариант лучше, поэтому гистограмма, которая в итоге будет сохранена, будет следующей:
Блок 1: Диапазон (1–4), Средняя частота 3,25
Блок 2: Диапазон (5–8), Средняя частота 2,5
Гистограммы V-optimal лучше справляются с оценкой содержимого контейнера. Гистограмма — это оценка базовых данных, и любая гистограмма будет иметь ошибки. Правило разбиения, используемое в гистограммах VOptimal, пытается получить наименьшую возможную дисперсию среди контейнеров, что обеспечивает меньшую ошибку. Исследования, проведенные Пусалой и Иоаннидисом 1, показали, что наиболее точная оценка данных выполняется с помощью гистограммы VOptimal, использующей значение в качестве параметра сортировки и частоту в качестве исходного параметра.
Хотя гистограмма V-optimal более точна, у нее есть недостатки. Это сложная структура для обновления. Любые изменения исходного параметра потенциально могут привести к необходимости полностью перестроить гистограмму, а не обновлять существующую гистограмму. Гистограмма равной ширины не имеет этой проблемы. Гистограммы равной глубины будут испытывать эту проблему в некоторой степени, но поскольку конструкция равной глубины проще, ее поддержание обходится дешевле. Сложность обновления гистограмм VOptimal является следствием сложности, связанной с построением этих гистограмм.
Вычисление V-оптимальной гистограммы требует больших вычислительных затрат по сравнению с другими типами гистограмм. [2]
Приведенный выше пример прост. Существует всего 7 вариантов границ блоков. Можно легко вычислить кумулятивную дисперсию для всех 7 вариантов и выбрать абсолютно лучшее размещение. Однако по мере того, как диапазон значений становится больше, а количество блоков увеличивается, набор возможных гистограмм растет экспоненциально, и становится пугающе сложной задачей найти набор границ, которые обеспечивают абсолютный минимум дисперсии, используя наивный подход. Используя динамическое программирование , можно вычислить V-оптимальную гистограмму, где N — количество точек данных, а B — количество блоков. [3]
Поскольку поиск оптимальной гистограммы является квадратичным, обычно вместо этого аппроксимируют V-оптимальную гистограмму. Создавая случайные решения, используя их в качестве отправной точки и улучшая их, можно найти решение, которое является справедливым приближением «лучшего» решения. Одним из методов построения, используемых для обхода этой проблемы, является алгоритм итеративного улучшения. Другим является имитация отжига. Оба могут быть объединены в двухфазной оптимизации, или 2PO. Эти алгоритмы изложены в «Рандомизированных алгоритмах...» (цитируется ниже) как метод оптимизации запросов, но общая идея может быть применена к построению V-оптимальных гистограмм.
Итеративное улучшение (II) — довольно наивный жадный алгоритм. Начиная со случайного состояния, рассматриваются итерационные шаги во многих направлениях. Выбирается шаг, который предлагает наилучшее улучшение стоимости (в данном случае общей дисперсии). Процесс повторяется до тех пор, пока не будет достигнут локальный минимум, где дальнейшее улучшение невозможно. Применительно к построению V-оптимальных гистограмм начальное случайное состояние будет набором значений, представляющих размещение границ контейнеров. Итерационные шаги улучшения будут включать перемещение каждой границы до тех пор, пока она не достигнет своего локального минимума, а затем перемещение к следующей границе и ее соответствующую корректировку.
Базовое объяснение имитации отжига заключается в том, что она во многом похожа на II, только вместо того, чтобы каждый раз делать жадный шаг, она иногда принимает шаг, который приводит к увеличению стоимости. Теоретически SA с меньшей вероятностью остановится на очень локальном минимуме и с большей вероятностью найдет более глобальный. Полезным изображением является график в форме M, представляющий общую стоимость на оси Y. Если начальное состояние находится на V-образной части «M», II расположится в высокой долине, локальном минимуме. Поскольку SA принимает подъемные движения, она с большей вероятностью поднимется по склону «V» и окажется у подножия «M», глобального минимума.
Двухфазная оптимизация, или 2PO, объединяет методы II и SA. II выполняется до тех пор, пока не будет достигнут локальный минимум, затем для этого решения выполняется SA в попытке найти менее очевидные улучшения.
Идея V-оптимальных гистограмм заключается в минимизации дисперсии внутри каждого блока. При рассмотрении этого возникает мысль, что дисперсия любого набора с одним членом равна 0. Это идея, лежащая в основе "End-Biased" V-оптимальных гистограмм. Значение с самой высокой частотой всегда помещается в свой собственный блок. Это гарантирует, что оценка для этого значения (которое, вероятно, будет наиболее часто запрашиваемой оценкой, поскольку это наиболее частое значение) всегда будет точной, а также удаляет значение, которое с наибольшей вероятностью вызовет высокую дисперсию из набора данных.
Другая мысль, которая может возникнуть, заключается в том, что дисперсия будет уменьшена, если сортировать по частоте, а не по значению. Это естественным образом приведет к размещению подобных значений рядом друг с другом. Такая гистограмма может быть построена с использованием значения сортировки частоты и исходного значения частоты. Однако на этом этапе блоки должны нести дополнительную информацию, указывающую, какие значения данных присутствуют в блоке. Было показано, что эти гистограммы менее точны из-за необходимости дополнительного уровня оценки.
