V-оптимальные гистограммы - V-optimal histograms

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

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

Определение

V-оптимальная гистограмма основана на концепции минимизации количества, которое в этом контексте называется взвешенной дисперсией . Это определяется как

${\ Displaystyle W = \ сумма _ {j = 1} ^ {J} n_ {j} V_ {j} \ ,,}$

где гистограмма состоит из J интервалов или корзин, n _j - количество элементов, содержащихся в j- м интервале, а V _j - дисперсия между значениями, связанными с элементами в j- м интервале.

Примеры

В следующем примере будет построена V-оптимальная гистограмма, имеющая значение сортировки значения, исходное значение частоты и класс раздела 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-оптимальности перед равной шириной или равной глубиной

V-оптимальные гистограммы лучше справляются с оценкой содержимого корзины. Гистограмма - это оценка базовых данных, и любая гистограмма будет содержать ошибки. Правило разделения, используемое в гистограммах VOptimal, пытается иметь наименьшую возможную дисперсию между сегментами, что обеспечивает меньшую ошибку. Исследование, проведенное Поосалой и Иоаннидисом 1 , продемонстрировало, что наиболее точная оценка данных выполняется с помощью гистограммы VOptimal с использованием значения в качестве параметра сортировки и частоты в качестве параметра источника.

Недостатки V-оптимальности по сравнению с одинаковой шириной или одинаковой глубиной

Хотя V-оптимальная гистограмма более точна, у нее есть недостатки. Это сложная структура для обновления. Любые изменения исходного параметра могут потенциально привести к необходимости полностью перестроить гистограмму, а не обновлять существующую гистограмму. Гистограмма одинаковой ширины не имеет этой проблемы. Гистограммы с одинаковой глубиной в некоторой степени столкнутся с этой проблемой, но поскольку конструкция с одинаковой глубиной более проста, ее обслуживание обходится дешевле. Сложность обновления гистограмм VOptimal является результатом сложности построения этих гистограмм.

Вычисление V-оптимальной гистограммы требует больших вычислительных ресурсов по сравнению с другими типами гистограмм.

Строительные вопросы

Приведенный выше пример простой. Есть только 7 вариантов границ ковша. Можно легко вычислить совокупную дисперсию для всех 7 вариантов и выбрать абсолютно лучшее размещение. Однако по мере того, как диапазон значений становится больше, а количество сегментов увеличивается, набор возможных гистограмм растет экспоненциально, и становится чрезвычайно сложной проблемой найти набор границ, обеспечивающих абсолютную минимальную дисперсию, с использованием наивного подхода. Используя динамическое программирование , можно вычислить V-оптимальную гистограмму, где N - количество точек данных, а B - количество сегментов. ${\ displaystyle O (N ^ {2} B)}$

Поскольку поиск оптимальной гистограммы является квадратичным, обычно вместо этого аппроксимируют V-оптимальную гистограмму. Создавая случайные решения, используя их в качестве отправной точки и улучшая их, можно найти решение, которое является точным приближением к «лучшему» решению. Одним из методов построения, используемых для решения этой проблемы, является алгоритм итеративного улучшения. Другой - имитация отжига. Оба могут быть объединены в двухфазную оптимизацию или 2PO. Эти алгоритмы представлены в «Рандомизированных алгоритмах ...» (цитируются ниже) как метод оптимизации запросов, но общая идея может быть применена для построения V-оптимальных гистограмм.

Итерационное улучшение

Итеративное улучшение (II) - довольно наивный жадный алгоритм. Рассматриваются итерационные шаги во многих направлениях, начиная со случайного состояния. Выбирается шаг, который предлагает наилучшее улучшение стоимости (в данном случае - общая дисперсия). Процесс повторяется до тех пор, пока один не установится на локальном минимуме, где дальнейшее улучшение невозможно. Применительно к построению V-оптимальных гистограмм начальное случайное состояние будет набором значений, представляющих размещение границ сегмента. Шаги итеративного улучшения будут включать перемещение каждой границы до тех пор, пока она не достигнет своего локального минимума, затем переход к следующей границе и ее соответствующая корректировка.

Имитация отжига

Основное объяснение имитации отжига состоит в том, что он очень похож на II, только вместо того, чтобы каждый раз делать жадный шаг, он иногда принимает шаг, который приводит к увеличению стоимости. Теоретически SA с меньшей вероятностью остановится на очень локальном минимуме и с большей вероятностью найдет более глобальный минимум. Полезным элементом изображения является график в форме буквы «М», представляющий общую стоимость по оси Y. Если исходное состояние находится на V-образной части буквы «M», II перейдет в высокую долину, локальный минимум. Поскольку SA будет принимать подъемы, она с большей вероятностью поднимется по склону "V" и окажется у подножия "M", глобального минимума.

Двухэтапная оптимизация

Двухфазная оптимизация, или 2PO, объединяет методы II и SA. II запускается до тех пор, пока не будет достигнут локальный минимум, затем для этого решения запускается SA в попытке найти менее очевидные улучшения.

Вариация

Идея V-оптимальных гистограмм состоит в том, чтобы минимизировать дисперсию внутри каждого сегмента. При этом возникает мысль, что дисперсия любого набора с одним элементом равна 0. Это идея, лежащая в основе V-оптимальных гистограмм с конечным смещением. Значение с самой высокой частотой всегда помещается в отдельную корзину. Это гарантирует, что оценка для этого значения (которая, вероятно, будет наиболее часто запрашиваемой оценкой, поскольку это наиболее частое значение) всегда будет точной, а также удалит значение, которое, скорее всего, вызовет высокую дисперсию из набора данных.

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

использованная литература

Процитированные работы

• Poosala, V .; Haas, PJ ; Иоаннидис, YE; Шекита, EJ (1996). «Улучшенные гистограммы для оценки избирательности предикатов диапазона». Материалы международной конференции ACM SIGMOD 1996 г. по управлению данными - SIGMOD '96 . п. 294. DOI : 10,1145 / 233269,233342 . ISBN 978-0897917940. S2CID  2948277 .Скачать PDF
• Иоаннидис, YE; Поосала, В. (1995). «Баланс оптимальности и практичности гистограммы для оценки размера результата запроса». Материалы международной конференции ACM SIGMOD по управлению данными 1995 г. - SIGMOD '95 . п. 233. DOI : 10,1145 / 223784,223841 . ISBN 978-0897917315. S2CID  15298037 .Скачать PDF
• Иоаннидис, YE; Канг Ю. (1990). «Рандомизированные алгоритмы для оптимизации больших запросов соединения». ACM SIGMOD Запись . 19 (2): 312. DOI : 10,1145 / 93605,98740 .Скачать PDF