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

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

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

Определение

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

W=\sum _{j=1}^{J}n_{j}V_{j}\,,

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

Примеры

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

Вопросы строительства

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

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

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

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

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

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

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

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

Вариация

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

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

Ссылки

^ Пусала и др. (1996)
^ Мусави, Хамид; Дзаньоло, Карло (21 марта 2011 г.). «Быстрое и точное вычисление гистограмм равной глубины по потокам данных» . Материалы 14-й Международной конференции по расширению технологий баз данных . EDBT/ICDT '11. Уппсала, Швеция: Ассоциация вычислительной техники. стр. 69–80. дои : 10.1145/1951365.1951376 . ISBN 978-1-4503-0528-0 . S2CID 6790310 .
^ Джагадиш, Х.В.; Цзинь, Хуэй; Оой, Бенг Чин; Тан, Киан-Ли (1 мая 2001 г.). «Глобальная оптимизация гистограмм» . Материалы международной конференции ACM SIGMOD 2001 г. по управлению данными . СИГМОД '01. Санта-Барбара, Калифорния, США: Ассоциация вычислительной техники. стр. 223–234. дои : 10.1145/375663.375687 . ISBN 978-1-58113-332-5 . S2CID 52857204 .

Цитируемые работы

Поосала, В.; Хаас, Пи Джей ; Иоаннидис, Ю.Е.; Шекита, Э.Дж. (1996). «Улучшенные гистограммы для оценки избирательности предикатов диапазона». Материалы международной конференции ACM SIGMOD 1996 года по управлению данными - SIGMOD '96 . п. 294. дои : 10.1145/233269.233342 . ISBN 978-0897917940 . S2CID 2948277 . Скачать PDF
Иоаннидис, Ю.Е.; Поосала, В. (1995). «Баланс оптимальности и практичности гистограммы для оценки размера результата запроса». Материалы международной конференции ACM SIGMOD 1995 года по управлению данными - SIGMOD '95 . п. 233. дои : 10.1145/223784.223841 . ISBN 978-0897917315 . S2CID 15298037 . Скачать PDF
Иоаннидис, Ю.Е.; Канг, Ю. (1990). «Рандомизированные алгоритмы для оптимизации больших запросов соединения». Запись ACM SIGMOD . 19 (2): 312. дои : 10.1145/93605.98740 . Скачать PDF

[1] Пусала и др. (1996)

[2] Мусави, Хамид; Дзаньоло, Карло (21 марта 2011 г.). «Быстрое и точное вычисление гистограмм равной глубины по потокам данных» . Материалы 14-й Международной конференции по расширению технологий баз данных . EDBT/ICDT '11. Уппсала, Швеция: Ассоциация вычислительной техники. стр. 69–80. дои : 10.1145/1951365.1951376 . ISBN 978-1-4503-0528-0 . S2CID 6790310 .

[3] Джагадиш, Х.В.; Цзинь, Хуэй; Оой, Бенг Чин; Тан, Киан-Ли (1 мая 2001 г.). «Глобальная оптимизация гистограмм» . Материалы международной конференции ACM SIGMOD 2001 г. по управлению данными . СИГМОД '01. Санта-Барбара, Калифорния, США: Ассоциация вычислительной техники. стр. 223–234. дои : 10.1145/375663.375687 . ISBN 978-1-58113-332-5 . S2CID 52857204 .

[1]

[2]

[3]