Аннотация

История гистограмм является длинной и насыщенной, наполненной детальной информацией на каждом шаге. Она включает применение гистограмм в разных областях науки, успехи и неудачи применения гистограмм при аппроксимировании и сжатии информации, принятие гистограмм в промышленности и решения большого числа проблем, связанных с гистограммами. В этой статье в духе самих методов гистограмм мы сжимаем всю их историю (включая их "будущую историю", как она представляется сегодня) в заданный/фиксированный объем текста, регистрируя, главным образом, детали временных промежутков, событий и результатов, представляющих наивысший интерес (с точки зрения автора). При ограниченном числе проведенных экспериментов семантическое расстояние между сжатой и полной формами истории оказалось относительно небольшим!

1. Предыстория

Слово 'гистограмма' происходит из Греции и состоит из слов 'isto-s' (ιστοs) (= 'столб', также это слово обозначает 'паутину', но это не существенно для нашего обсуждения) и 'gram-ma' (γραμμα) (= 'нечто записанное'). Следовательно, термин следует интерпретировать, как некую форму записи, состоящую из 'столбиков', т.е. продолговатых, вертикально расположенных фигур. Однако это слово изначально не использовалось в греческом языке.¹ Термин 'гистограмма' был введен знаменитым статистиком Карлом Пирсоном (Karl Pearson)² для обозначения "общей формы графического представления". В цитате Оксфордского словаря английского языка из "Philosophical Transactions of the Royal Society of London" Series A, Vol. CLXXXVI, (1895) p. 399" упоминается, что "[Слово 'гистограмма' было] введено автором лекций по статистике как термин для обозначения общей формы графического представления, т.е. путем маркировки столбцов как областей частотности в соответствии с масштабом их базиса". Стинглер отождествляет упомянутые лекции с изданными в 1892 г. лекциями по статистической геометрии [69].

Приведенная цитата говорит о том, что гистограммы использовались задолго до того, как получили свое имя, но их дата рождения неясна. Столбчатые диаграммы (bar chart), т.е. гистограммы, в которых с каждым столбцом ассоциируется отдельный 'базисный' элемент, скорее всего, предшествуют гистограммам, и это помогает нам установить нижнюю временную границу их первого появления. Наиболее древняя столбчатая диаграмма появилась в книге шотландского политического экономиста Уильяма Плейфейра (William Playfair)³ "The Commercial and Political Atlas" (London 1786), в которой демонстрируются показатели импорта и экспорта Шотландии в семнадцать стран в 1781 г. [74]. Хотя Плейфейр относился к своему изобретению скептически, в последующие годы оно было принято многими, включая Флоренса Найтингейла (Florence Nightingale), который использовал их в 1859 г. для сравнения смертности в армии в мирное время со смертностью гражданского населения, и путем этого убедил правительство улучшить гигиенические условия в армии.

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

В последние два десятилетия гистограммы использовались в нескольких областях информатики. Кроме области баз данных, гистограммы играют важную роль, главным образом, в областях обработки изображений и машинного зрения. При заданном изображении (или видео) и визуальном пиксельном параметре, гистограмма фиксирует для каждого возможного значения параметра ("класса" по Вебстеру) число пикселей, имеющихся у этого значения ("частота" по Вебстеру). Такая гистограмма является сводной характеристикой изображения и может быть очень полезна при решении нескольких задач: распознавании похожих изображений, сжатии изображений и т.д. В литературе наиболее распространены диаграммы цветов, например, в системе QBIC [21], но было предложено и несколько других параметров, например, плотность границ, текстурность, градиент яркости и т.д. [61]. Вообще говоря, гистограммы, используемые в областях обработки изображений и машинного зрения, являются точными. Например, в гистограмме цветов содержится раздельное и точное число пикселей для каждого возможного отдельного цвета изображения. Единственным элементом аппроксимации могло бы быть число бит, используемых для представления различных цветов: наличие меньшего числа бит означает, что несколько реальных цветов будет изображаться одним цветом, ассоциируемым с числом пикселей, которое имелось бы совместно у всех заменяемых таким образом цветов. Однако даже такая разновидность аппроксимации не является распространенной. В области баз данных гистограммы используются как механизм выровненного по краям сжатия и аппроксимации распределений данных. В литературе и системах они появились в 1980-х и впоследствии изучались с возрастающей интенсивностью. В этой статье мы концентрируемся на понятии гистограмм, принятом в области баз данных, обсуждаем наиболее важные разработки, относящиеся к этой теме, и кратко характеризуем несколько проблем, которые считаем интересными, и решение которых может еще более расширить применимость и полезность гистограмм.

2. Определения гистограмм

2.1 Распределения данных

Рассмотрим отношение R с n числовыми атрибутами X_i(i = 1.. n). Множество значений V_i атрибута X_i - это множество значений X_i, присутствующих в R. Пусть V_i = {v_i (k): 1 ≤ k ≤ D_i}, где v_i(k) < v_i(j) при k < j. Протяженность (spread) s_i(k) для v_i(k) определяется как s_i(k) = v_i(k+1) - v_i(k) для 1 ≤ k < D_i. (Мы полагаем s_i(D_i) = 1). Частота f_i(k) для v_i(k)- это число кортежей в R с X_i = v_i(k). Площадь (area) a_i(k) для v_i(k) определяется как a_i(k) = f_i(k)• s_i(k).

Распределение данных для X_i - это множество пар T_i = {(v_i (1), f_i(1)), (v_i(2), f_i(2)), …, (v_i(D_i ), f_i(D_i))}.

Соединенная частота (joint frequency) f(k₁, …, k_n) комбинации значений < v₁(k₁), …, vn(k_n) >- это число кортежей в R, в которых для всех i атрибут X_i содержит значение v_i(k_i). Соединенное распределение данных T_1,…,n для X₁,…,X_n - это полное множество пар (комбинация значение, соединенная частота).

Далее для одномерного случая мы будем использовать введенные обозначения без нижнего индекса i.

2.2 Обоснование гистограмм

Распределения данных очень полезны в системах баз данных, но обычно они слишком велики, чтобы можно было хранить их точно, так что в игру вступают гистограммы как механизм аппроксимации. Методы гистограмм в базах данных наиболее важны для оценок селективности и формировании приблизительных ответов на запросы в оптимизаторе запросов (для первого случая) и при организации обратной связи с пользователями до выполнения запросов (для обоих случаев). Наше дальнейшее обсуждение сосредотачивается именно на этих двух случаях, и в особенности на оценки селективности диапазонных запросов (range-query), поскольку эта тема наиболее популярна в литературе. Однако не следует забывать, что показана полезность гистограмм и в контексте нескольких других проблем баз данных, например, при балансировке нагрузки при параллельном выполнении запросов [65], выполнении темпоральных соединений на основе разделов [68] и т.д.

2.3 Гистограммы

Гистограмма на атрибуте X конструируется путем разделения распределения данных для X на β (≤ 1) взаимно непересекающихся подмножеств, называемых бакетами (bucket) и аппроксимирующих частоты и значения в каждом бакете в некоторой общей манере. Это определение оставляет несколько степеней свободы при разработке конкретных классов гистограмм, поскольку имеется несколько вариантов выбора для каждого из следующих (большей частью, ортогональных) аспектов гистограмм [67]:

Правило разделения: Здесь можно выделить следующие характеристики:

• Класс разделения: Эта характеристика показывает, имеются ли какие-либо ограничения на бакеты. Огромной важностью обладают сериальный класс разделения, который требует, чтобы бакеты были не перекрывающимися в соответствии с некоторым параметром, и его подкласс - класс разделения со смещением к краям (end-biased), для которого требуется наличие не более одного одноэлементного бакета.
• Параметр разделения (Sort Parameter): Это параметр, значение которого для каждого элемента распределения данных порождается из соответствующего значения атрибута и частот. Для всех сериальных гистограмм требуется, чтобы значения параметра разделения в каждом бакете образовывали непрерывный диапазон. Примерами параметров разделения, обсуждаемыми в литературе, являются значение атрибута (V), частота (F) и площадь (A).
• Параметр источника (Source Parameter): В этом параметре фиксируется свойство распределения данных, являющееся наиболее важным для проблемы оценки и используемое совместно со следующей характеристикой при определении уникального разделения. Наиболее часто используемыми параметрами источника являются протяженность (S), частота (F) и площадь (A).
• Ограничение разделения (Partition Constraint): Это математическое ограничение на параметр источника, которое уникально идентифицирует гистограмму в ее классе разделений. Предлагалось несколько ограничений разделения, например, equi-sum, v-optimal, maxdiff и compressed, которые мы определяем ниже так, как они вводились авторами. Во многих наиболее удачных подходах авторы старались избежать группирования в бакет чрезмерно различные значения параметра источника.

Следуя [67], мы используем p(s,u) для обозначения сериального класса гистограмм с ограничением разделения p, параметром разделения s и параметром источника u.

Алгоритм конструирования: Это алгоритм, который по заданному правилу разделения конструирует гистограммы, соответствующие этому правилу. Часто для одного класса гистограмм существует несколько алгоритмов конструирования с разной эффективностью.

Аппроксимация значений: В этом аспекте фиксируется то, как внутри бакета аппроксимируются значения атрибута, что не зависит от правила разделения гистограммы. Наиболее распространенными альтернативами являются предположение о непрерывности значений (continuous value assumption) и предположение о равномерности протяженностей (uniform spread assumption); в обоих случаях предполагается, что значения равномерно размещаются в диапазоне, покрываемом бакетом, но в первом случае игнорируется число этих значений, а во втором это число регистрируется внутри бакета.

Аппроксимация частоты: В этом аспекте фиксируется то, как внутри бакета аппроксимируются частоты. Доминирующий подход опирается на предположение о равномерности частот (uniform distribution assumption), в котором предполагается, что частоты всех элементов в бакете одни и те же и равны среднему значению реальных частот.

Гарантии ошибок: Имеются верхние границы ошибок оценок, производимых гистограммой, обеспечиваемые на основе информации, которую поддерживает гистограмма.

Многомерная гистограмма на множестве атрибутов конструируется путем разделения соединенного распределения данных этих атрибутов. У таких гистограмм имеются точно такие же характеристики, как и у одномерных гистограмм, за исключением того, что требуется более сложное разделения, и оно не всегда так отчетливо раскладывается в четыре других характеристики, как раньше, например, в этом случае нет реального параметра разделения, поскольку в многомерном пространстве не может быть упорядоченности [66].

3. Прошлое гистограмм

Первое появление

Насколько нам известно, первое предложение по использованию гистограмм для аппроксимирования распределений данных в системе баз данных появилось в PhD-диссертации Куи (Kooi) [47]. Его предложение состояло в непосредственном заимствовании из статистик простейшей формы гистограммы, в которой множество значений разбивалось на диапазоны одинаковой длины, т.е. диаграммы с одинаковой шириной (equi-width histogram). Следовательно, в терминах таксономии из разд. 2.3 точкой входа гистограмм в мир баз данных явился сериальный класс равных сумм (equi-sum(V,S)), где ограничение разделения equi-sum требует, чтобы суммы значений параметра источника (в данном случае - протяженности) были для каждого бакета одними и теми же. Внутри каждого бакета значения и частоты аппроксимировались на основе предположений о непрерывности значений и равномерности распределения частот.

Гистограммы с одинаковой шириной представляли собой существенное усовершенствование предположения о равномерном распределении для всего множества значений (т.е., по существу, гистограммы с единственным бакетом), на котором в то время основывались практические системы. Поэтому они были быстро внедрены сначала в коммерческую версию СУБД Ingres, а потом и в другие СУБД.

Первая альтернатива

Через несколько лет после появления работы Куи была предложена первая альтернативная диаграмма, в которой изменялся только параметр источника [62]. Вместо использования бакетов с диапазонами одинаковой длины предлагалось применять бакеты, каждому из которых соответствовало (грубо говоря) одно и то же число кортежей, т.е. предлагалось использовать так называемые гистограммы с одинаковой глубиной (equi-depth), или одинаковым весом. В терминах нашей таксономии эти гистограммы относятся к классу equisum(V,F). Было достаточно очевидно, что гистограммы с одинаковой глубиной существенно более эффективнее гистограмм с одинаковой шириной, и поэтому многие коммерческие поставщики в последующие годы перешли к их использованию. Позже был представлен многомерный вариант гистограмм с одинаковой глубиной [58].

Оптимальный параметр разделения

После нескольких лет пассивности по отношению к теме гистограмм интерес возбудился в контексте изучения того, как исходные ошибки в статистике, поддерживаемой системой баз данных, распространяются на оценки результатов сложных запросов [36]. В частности, было показано, что при некоторых, достаточно общих условиях в худшем случае ошибки в оценке размера результата запроса распространяются экспоненциально (от числа соединений), что устраняет какую-либо надежду на высококачественные оценки для сложных запросов с несколькими соединениями. Первые результаты, которые вели к новым типам гистограмм, были получены при попытке получения статистики, которая была бы оптимальна при минимизации/сдерживании распространения ошибок в размере результата соединений [37]. Основной использованный математический аппарат был позаимствован из теории мажорирования [55]. Внимание в основном уделялось ограниченному классу запросов с эквисоединениями, т.е. запросов с одним или несколькими соединениями, в которых в соединении участвует только один атрибут каждого отношения (в более общей постановке, между каждой парой атрибутов соединения каждого отношения существует функциональная зависимость "1-1"). Для этого класса запросов в предположении наличия точного знания множества значений было формально доказано, что оптимальная гистограмма является сериальной с частотой в качестве параметра разделения.⁴

Десять лет тому назад

Упомянутый выше результат мог бы не иметь влияния, если бы данное утверждение было истинным только для того ограниченного класса запросов, для которого оно было изначально доказано. Однако на VLDB'93 утверждение было обобщено для произвольных запросов с эквисоединением, что отчетливо показало, что наиболее эффективные гистограммы могут существенно отличаться от тех, которые использовались ранее [34].

Насколько нам известно, гистограммы с частотой в качестве параметра разделения представляли первое отклонение от группировки бакетов на основе значений не только в области баз данных, но также и в математике и статистике. Кроме того, их введение позволило существенно обобщить некоторые распространенные практические приемы, которые уже использовались в коммерческих системах (например, в DB2), где информация о значениях с наибольшей частотой поддерживалась индивидуально и точно по причине ее важности для оценки селективности. Такой прием является примером особого вида гистограммы с классом разделения со смещением к краю и частотой в качестве параметра разделения: значения с наивысшим значением параметра разделения поддерживаются в одиночных бакетах. Хотя в нескольких случаях гистограммы со смещением к краю оказываются менее точными, чем общие сериальные гистограммы, они достаточно эффективны.

Новые ограничения разделения

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

Ответ на первый вопрос поступил в форме v-оптимальных (v-optimal) гистограмм, которые разделяют распределение данных таким образом, что (грубо говоря) минимизируется дисперсия значений параметра источника внутри каждого бакета [38].

К сожалению, аналитический ответ на второй вопрос отсутствует, но большое число экспериментов привело к формированию пространства характеристик гистограмм, которое мы используем в качестве основы обсуждения в данной статье (разд. 2.3) [67]. В дополнение к ограничениям разделения equi-sum и v-optimal было введено несколько новых возможных ограничений, целью которых, аналогично v-optimal, являлось избежание группировки в одном бакете слишком разных значений параметра источника. Среди этих ограничений мы выделяем ограничение maxdiff, которое устанавливает границы бакетов между соседними значениями параметра источника (в порядке параметра разделения) с наибольшей разностью, и compressed, которое помещает наибольшие значения источника в одиночные бакеты и разделяет оставшиеся значения в стиле equi-sum. В целом, было показано, что новые ограничения разделения (т.е. v-optimal, maxdiff и compressed) являются наиболее эффективными при сдерживании ошибок в оценках размеров результатов запросов.

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

Наиболее эффективные из этих гистограмм реально внедрены в промышленные продукты (см. разд. 4). Кроме того, в дополнение к оценке селективности для различных реляционных и не реляционных запросов эти гистограммы оказались очень эффективными и при обеспечении приблизительные ответы на запросы [39].

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

Альтернативные ограничения разделения

В добавление к ограничениям разделения, введенным в составе исходного каркаса гистограмм[67], было предложено несколько других ограничений, претендующих на достижение эффективности ограничения v-optimal при более приемлемой стоимости конструирования. Мы отметим одно из этих ограничений, в котором используется упрощенная форма проблемы оптимального размещения узлов [18] для определения границ бакетов, которые устанавливаются в соответствии с размещением узлов [46]. Упрощение состоит в использовании только линейных сплайнов, в которых, кроме того, допускаются разрывы на границах бакетов. Это комбинируется с интересными альтернативами по аппроксимации значений и частот внутри каждого бакета.

Правила многомерных разделений

Многомерные гистограммы были впервые введены Мураликришной и ДеВиттом (Muralikrishna и DeWitt) [58], которые, по существу, описали двухмерные гистограммы с одинаковой глубиной. Пространство разделялось таким же образом, как это делается в Grid-файлах, т.е. путем рекурсивного разрезания всего пространства на два подпространства, каждый раз с использованием в качестве границы значения одного измерения. Измерение и значение выбирались способом, предписанным в начале этого процесса [58]. Бакеты были неперекрывающимися (многомерный вариант сериального класса разделения) в пространстве многомерных значений (многомерный вариант значения как параметра разделения).

Только несколько лет спустя были предложены некоторые новые правила разделения [66], которые опирались на универсализм таксономии гистограмм [67]. Наиболее эффективным семейством таких правил было MHIST-2, которое начинает со всего распределения данных, размещенного в одном бакете, и на каждом шаге расщепляет пространство, занимаемое одним из сформированных ранее бакетов, на два подпространства, пока не исчерпается бюджет бакетов. Расщепление производится в том бакете и по тому измерению, которые характеризуются как наиболее "критические", т.е. частное распределение (marginal distribution) которых больше всего нуждается в разделении. Расщепление основывается на используемых (одномерном) ограничении разделения и параметре источника. В сочетании с наиболее эффективными ограничениями разделения (т.е. с v-optimal или maxdiff с частотой или площадью) MHIST-2 представляет значительное усовершенствование исходных многомерных гистограмм с одинаковой глубиной.

После появления MHIST было предложено много интересных правил разбиения. Одним из них является семейство правил GENHIST [31], которое изначально было предложено в контексте многомерных вещественных данных, но его применимость оказалась более широкой. Основная характеристика GENHIST состоит в том, что оно допускает перекрытие бакетов в пространстве многомерных значений: алгоритм начинает свою работу с равномерного сеточного разделения (grid partitioning) пространства, а затем итеративно укрупняет бакеты, содержащие большое число элементов данных. Это порождает два эффекта: во-первых, уменьшается плотность данных в каждом бакете, что сглаживает плотность в целом; во-вторых, бакеты становятся перекрывающимися, что приводит к созданию гораздо большего числа различных областей, чем число самих бакетов. Аппроксимацией распределения данных внутри каждой области является комбинация того, что показывают все перекрывающиеся бакеты, образующие данную область. В результате при небольшом числе бакетов обеспечиваются аппроксимации с низким уровнем ошибок.

Альтернативным подходом является STHoles Histogram [11], который дуален по отношению к GENHIST: вместо области, покрываемой бакетом увеличивающегося размера и перекрывающегося с другими бакетами, в STHoles эта область может уменьшаться в размере благодаря удалению ее части (т.е. открытия отверстия (opening a hole)), образующей отдельный, дочерний бакет. Это приводит к порождению бакетов, не являющихся сплошными прямоугольниками, и тем самым позволяет фиксировать достаточно нерегулярные распределения данных.

Определение эффективных правил многомерного разделения ни в коем случае не является закрытой проблемой; непрерывно предлагаются различные подходы [23].

Аппроксимация значений внутри каждого бакета

При заданном объеме пространства под гистограмму одним из основных компромиссов является сочетание числа бакетов и объема информации, сохраняемой в каждом бакете. Малый объем информации внутри каждого бакета влечет грубые локальные аппроксимации и большее число бакетов. Ключевым вопросом является нахождение правильного баланса в этом компромиссе для оптимизации общей аппроксимации распределения данных.

По отношению к аппроксимации множества значений, попадающих в одномерный бакет, имеются два подхода. При традиционном предположении о непрерывности значений поддерживается наименьший объем информации (только минимальное и максимальное значения), но ничего такого, что могло бы каким-то образом подсказать, сколько значений имеется, и какими они могли бы быть. При использовании более современного предположения о равномерности промежутков [67] также поддерживается число значений внутри каждого бакета, и реальное множество значений аппроксимируется множеством, формируемым путем (виртуального) размещения того же числа значений на равных расстояниях между минимальным и максимальным значениями. В другом варианте этого подхода предлагается сохранять не реальную среднюю протяженность внутри бакета, а протяженность, которая сокращает уровень ошибки общей аппроксимации при запросах по диапазонам значений, принимая во внимание распространенность конкретных диапазонов внутри каждого бакета [46]. Имеется несколько исследований, показывающих превосходство каждого из общих методов над другим; это свидетельствует о том, что абсолютного победителя может и не существовать.

Два упомянутых основных подхода расширены и на случай многомерных бакетов с поддержкой в бакете минимального и максимального значений каждого измерения. При использовании предположения о непрерывности значений больше ничего и не требуется, но при использовании предположения о равномерности промежутков возникает проблема: существование каких (многомерных) значений предполагается в бакете? Если d_i - это число различных значений в атрибуте X_i , присутствующих в бакете, и v_i '(k) - k-ое приближенное число в измерении i (полученное путем применения предположения о равномерности протяженности по этому измерению), то разумно предположить, что в бакете присутствуют все возможные комбинации <v₁'(k₁), …, v_n '(k_n )>, 1 ≤ k_i ≤ d_i [66].

В одной интересной исследовательской работе в мир одномерных гистограмм было введено использование стержневой оценки (kernel estimation) [10] специально для работы с вещественными данными. Грубо говоря, в этом методе предлагается выбирать точки существенного изменения функции плотности вероятности в качестве границ бакетов (в духе, напоминающем ограничение разделения maxdiff), а затем применять традиционный метод стержневой оценки для аппроксимирования значений внутри каждого бакета. Это также обобщено на многомерный случай [31].

Аппроксимация частоты внутри каждого бакета

По отношению ко множеству частот, попадающих в бакет, почти во всех исследовательских работах использовалось предположение о равномерном распределении. Одно из немногих исключений представляет работа, в которой комбинировалось применение упомянутого выше ограничение разделения линейных сплайнов и аппроксимации частот также на основе линейных сплайнов [46]. В этом методе для каждого бакета поддерживается дополнительный элемент данных, показывающий линейно возрастающие или убывающие частоты, ценой уменьшения числа в фиксированном бюджете пространства. Подобным образом, в другом исключительном случае внутри каждого бакета используется небольшое пространство одинакового размера для хранения накопленной частоты в четырехуровневом древовидном индексе [13]. Однако, в отличие от предыдущей работы, здесь этот подход комбинируется с некоторыми установившимися ограничениями разделения, т.е. v-optimal and maxdiff.

Эффективное и динамическое конструирование

Хотя эффективность оценок, по-видимому, является наиболее важной характеристикой гистограмм (и любого другого метода сжатия/оценивания), интерес представляет и стоимость конструирования. Что касается этого аспекта, гистограммы можно разделить на две категории: статические и динамические/адаптивные гистограммы. Статические гистограммы - это те, которые традиционно используются в системах баз данных: после их конструирования (на основе хранимых данных или образцов) они остаются неизменными, даже если изменяются исходные данные.

В зависимости от деталей изменения данных статические гистограммы рано или поздно расходятся с тем, что они должны аппроксимировать, и производимые на их основе оценки могут допускать все более серьезные ошибки. Когда это происходит, администраторы запускают пересчет гистограммы, и в этот момент старая гистограмма отбрасывается, а новая вычисляется заново. Важным аспектом статических гистограмм является сама стоимость вычисления, на которую, главным образом, влияет ограничение разделения. Для большинства таких ограничений (например, equi-sum, maxdiff, compressed) имеются эффективные и простые методы вычисления гистограмм. Однако это не так для ограничения, для которого показана его максимальная эффективность, т.е. для v-optimal; для этого случая стоимость вычисления в общем случае экспоненциально зависит от числа значений параметра источника. В этом отношении ключевым вкладом является предложение алгоритма, основанного на динамическом программировании, который определяет v-оптимальную гистограмму (для любых параметров разделения и источника) за время, квадратично зависимое от числа значений параметра источника и линейно зависимое от числа бакетов, что делает практичными и эти гистограммы [42]. Впоследствии было выполнено несколько работ (в основном теоретических), в которых предлагались алгоритмы, сокращающие время, требуемое для вычисления этих оптимальных гистограмм, сводя его, в конце концов, к линейному и достигая аналогичных усовершенствований и в отношение памяти [30]. Алгоритмы динамического программирования были также предложены для конструирования оптимальных гистограмм для (иерархических) запросов с диапазонами над OLAP-данными [44]. Для многомерного случая проблема определения оптимальной гистограммы NP-полна, поэтому было предложено несколько приблизительных методов [59].

В другой интересной работе были предложены алгоритмы для определения оптимальных наборов гистограмм (в противоположность к определению отдельных гистограмм), основанные на ожидаемой рабочей нагрузке [40]. Эта работа фокусируется на v-оптимальных гистограммах, но ее результаты равно применимы и к другим ограничениям разделения.

Однако даже при существовании эффективных алгоритмов вычисления статическим гистограммам свойственных возрастающие ошибки в промежутках между вычислениями. Более того, статические гистограммы вообще непригодны в среде потоков данных, поскольку отсутствует возможность сохранения поступающих данных и повторного их анализа. В связи с этим в нескольких работах предлагались различные подходы к поддержке динамических/адаптивных/самонастраивающихся гистограмм, которые изменяются при обновлении данных, оставаясь конкурентоспособными со статическими гистограммами. Среди этих работ мы отметим одну по поводу гистограмм, основанных на ограничениях разделения equi-depth и compressed [26], одну для v-оптимальных гистограмм [27] и одну для гистограмм, основанных на (линейных) сплайнах [46]. Имеется также исследовательская работа, фокусирующаяся на потоках данных, в которой поддерживается набросок (соединенного) распределения данных потока, на основе которого может быть сконструирована эффективная многомерная гистограмма [72]; в экспериментах использовались гистограммы STHoles, но в принципе метод можно применить и к другим классам диаграмм.

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

Эти работы обобщаются в системе LEO [70], поскольку в ней для обновления статистики используются размеры результатов намного более сложных запросов, включая запросы с соединениями и агрегацией, запросы с определенными пользователями функциями и т.д. Интересно, что LEO не обновляет статистику "по месту", а помещается информацию обратной связи в отдельные каталоги, которые используются в комбинации с исходными гистограммами во время проведения оценивания.

Гарантии ошибок

В большей части работ, посвященных гистограммам, речь идет об определении гистограмм, демонстрирующих низкий уровень ошибок в некоторой проблеме оценок, но не об обеспечении вместе с оценками некоторой информации о том, что из себя могли бы предоставлять эти ошибки. В первой работе, затрагивающей этот аспект [42], предлагается сохранять в каждом бакете максимальное значение разности между реальной и приближенной (обычно, средней) частотами значения в бакете и использовать это значение для обеспечения верхних границ ошибок любых оценок селективности на основе гистограмм для запросов со сравнениями по равенству и проверками вхождения в диапазон. Интересная альтернативная работа фокусируется на оптимизации запросов по диапазону категории top-N. В этой работе предлагается сохранять дополнительную информации для гистограммы целиком, а не на уровне бакетов [20].

Другие типы данных

Как отмечалось ранее, большая часть работ в области гистограмм фокусируется на аппроксимации численных значений в одном или нескольких измерениях (атрибутах). Тем не менее, потребность в аппроксимации гораздо шире, и в нескольких исследовательских работах анализируется использование гистограмм и для других типов данных.

По отношению к пространственным данным канонический подход к двухмерным гистограммам не срабатывает, поскольку он предназначен для точечных данных и не расширяется для объектов, которые двумерны сами по себе. Кроме того, частота обычно не является характеристикой пространственных данных, поскольку пространственные объекты не повторяются в базе данных. Было предложено несколько интересных методов для решения дополнительных проблем, которые обычно связаны с правилом разделения, т.е. тем, как пространственные объекты группируются в бакеты. При использовании некоторых методов бакеты формируются путем обобщения традиционных гистограммных ограничений разделения, в то время как в других методах это делается с применением пространственных индексов (например, R-деревьев). Среди наиболее сложных методов можно выделить MinSkew Histogram [5], в котором пространство разделяется путем использования двоичного разделения (на каждом шаге пространство разделяется по одному измерению), что минимизирует общую пространственную скошенность всех бакетов. Дисперсия плотности объектов сохраняется в каждом бакете, так что в некотором смысле этот метод построен в духе v-оптимальных гистограмм. Интересной альтернативой является метод SQ-Histogram [3], в соответствии с которым пространство разделяется по правилу Quad-tree (являющемуся более ограничительным, чем произвольное бинарное разделение), и, в добавок к пространственной близости, принимается во внимание близость размеров и сложность многоугольников (число вершин), помещаемых в один и тот же бакет. Метод MinSkew Histogram был расширен для фиксации скорости движения объектов и сделан пригодным для аппроксимации и пространственно-временных данных [17].

Текущий интерес к XML, конечно, не мог не коснуться XML-аппроксимации, оценок размера результатов запросов и других родственных проблем. Полуструктурированная природа XML сама по себе не приспособлена к применению аппроксимации на основе гистограмм, поскольку отсутствует непосредственное многомерное пространство, которое может разбиваться на бакеты, и требуется формировать некоторые численные характеристики XML. В подходе StatiX [22] используется информация XML Schema для определения потенциальных источников структурного скашивания, а затем строятся одномерные гистограммы для большей части проблемных мест схемы, позволяя аппроксимировать распределения идентификаторов родительских узлов для различных элементов. В подходе XPathLearner [49] используются марковские гистограммы (первого порядка) [1], где частоты обходов всех путей длины 2 сохраняются в двумерных гистограммах. Измерения всегда представляют узлы `from' и `to' путей в графе XML; в первой гистограмме оба узла/измерения являются тегами XML, в то время как во второй гистограмме узел/измерение `from' является тегом XML, а узел/измерение `to' - это значение. При наличии достаточного объема памяти для всех пар тег-тег частоты поддерживаются точно, поскольку их очень немного. В отличие от этого, пары <тег, значение> помещаются в гистограмму, основанную на двумерной версии ограничения разделения "compressed" с использованием частоты как параметра источника. В другом подходе к оценке размеров результатов запроса к XML-данным также строится позиционная гистограмма на двухмерном пространстве, но здесь оба измерения прямо или косвенно связываются с нумерацией каждого узла в предопределенном порядке обхода графа XML [79]. Наконец, гистограммы используются также для цели аппроксимации XML в комбинации с другими структурами данных (или в их составе). Достаточно эффективным основанным на графах подходом является XSketch, в котором предпринимается попытка фиксировать как структурные характеристики файлов XML, так и характеристики значений [63, 64]. Гистограммы используются в различных частях XSketch для фиксации статистических корреляций элементов и значений в заданных окрестностях Xsketch-графа.

В дополнение к использованию для графов XML, предлагается также применять их для фиксации степеней узлов в графах общего вида, что может служить способом сравнения графов и оценки их близости [60].

Нетрадиционные гистограммы

Временами встречались интересные работы, авторы которых не следовали общей таксономии гистограмм или определениям проблем гистограмм. В одной из этих работ предлагалось использовать дискретное косинусное преобразование (Discrete Cosine Transform, DCT) для сжатия всей многомерной гистограмм и хранить ее в сжатой форме [48]. Используется очень простое правило многомерного разделения (равномерная решетка на всем пространстве); пространство делится на большое число небольших бакетов, и затем информация бакетов сжимается с использованием DCT. Это позволяет сократить не только объем требуемой памяти, но и время оценки, поскольку необходимую информацию можно восстановить, интегрируя обратную функцию DCT.

Также имеется перспективное направление исследований, в котором гистограммы комбинируются с другими методами для обеспечения более высококачественных оценок, чем может обеспечить какой-либо метод в отдельности. В дополнение к нескольким таким комбинациям с применением взятия образцов, особенно интересный метод направлен на преодоление "проклятия размерности" (curse of dimensionality) путем определения решающих областей зависимости и независимости между измерениями в многомерных данных, фиксации их в статистической модели взаимодействий (например, нелинейной модели), которая затем может образовать основу для MHIST-гистограмм меньшей размерности, служащей для аппроксимации всего соединенного распределения данных [19].

Наконец, имеется очень интересное отступление от традиций, когда гистограммы строятся на базовых отношениях, и оценки распределений данных промежуточных результатов запросов получаются путем соответствующих манипуляций над этими гистограммами [12]. В этой работе обсуждается возможность поддержки гистограмм на результатах сложных запросов, что оказывается в некоторых случаях довольно эффективным. Для демонстрации предлагаемого подхода в работе используются основные гистограммы SQL Server (по существу, основанные на maxdiff - см. разд. 4), но основные результаты не зависят от конкретного класса гистограмм. Поскольку число потенциальных гистограмм сложных запросов гораздо больше числа гистограмм базовых отношений, соответственно более сложной является и проблема проектирования баз данных, когда решается, какие гистограммы следует конструировать. К счастью, для этих целей удается применить алгоритм, основанный на рабочей нагрузке.

4. Присутствие гистограмм в индустрии

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

В DB2 используются гистограммы класса compressed со значениями в качестве параметра разделения и частотой в качестве параметра источника [50]. Пользователи могут специфицировать число одноэлементных и неодноэлементных бакетов, желательных для наиболее частых значений, и, соответственно, часть гистораммы compressed с умолчанием от10 до 20. Отклонение от приведенного выше общего описания состоит в том, что в DB2 внутри неодноэлементных бакетов сохраняются накопленные частоты. Конструирование гистограммы основывается на образцах хранимых данных. В DB2 используется многомерная информация о мощности из индексов на составных атрибутах (когда они доступны) для получения количественных оценок зависимостей, которые могут существовать между атрибутами, и эти оценки используются в процессе оценивания селективности. При отсутствии таких оценок атрибуты считаются независимыми. Возможности обучения LEO [70] играют основную роль в том, как вся доступная информация используется для получения высококачественных оценок.

В Oracle все еще используются гистограммы с одинаковой шириной [78]. Основной подход к многомерной селективности похож на подход DB2 и основывается на использовании всякой информации из составных индексов. Однако, в дополнение к этому, поддерживаются средства динамического взятия образцов для получения при потребности "на лету" информации о зависимостях для сложных предикатов (в настоящее время это работает для предикатов ограничения и функций на одной таблице, а вариант для соединений будет доступен в следующем релизе системы). Также принимаются во внимание зависимости, существующие между атрибутами иерархий измерений куба при выполнении roll-up, и обеспечиваются оценки на соответствующем уровне иерархии. Наконец, в следующем релизе будут использоваться методы обучения для запоминания селективности обрабатывавшихся ранее предикатов и использования этих данных в будущем.

В SQL Server используются гистограммы maxdiff со значениями к качестве параметра разделения и, по существу, средней частоты (в каждом бакете) в качестве параметра источника [9]. Допускается до 199 бакетов, и внутри каждого бакета сохраняются частота максимального значения и (по существу) накопленная частота всех меньших значений. Гистограммы обычно конструируются на основе взятия образцов данных. Составные индексы используются в той же манере, что и в других системах, для получения многомерной информации о селективности.

Заметим, что во всех коммерческих СУБД реализуются строго одномерные гистограммы. За исключением применения некоторой второстепенной косвенной информации, в системах по-прежнему используется предположение о независимости значений атрибутов, и не используются многомерные гистограммы.

5. Конкуренты гистограмм

Основным методом, конкурирующим с гистограммами в последние десять лет являются вейвлеты, которые играют очень важную роль в области сжатия изображений, а в области баз данных начали применяться в конце 90-х [7, 56]. Вейвлеты широко используются для обеспечения приблизительных ответов на запросы разных типов и/или в различных средах: многомерные агрегатные запросы (range-sum queries) в средах OLAP [75, 76], агрегатные и не агрегатные запросы с вычислениями непосредственно над хранимыми коэффициентами вейвлетов [14] и ограничительные или агрегатные запросы над потоками [28]. Как и в случае гистограмм, предпринимаются усилия по разработке методов, основанных на вейвлетах, которые обеспечивают приблизительные ответы на запросы с гарантированным уровнем ошибок [24], а также методов динамического конструирования и поддержки наиболее важных коэффециентов вейвлетов [57].

Сэмплинг не является прямым конкурентом гистограмм, поскольку это, главным образом, метод времени выполнения (runtime technique), и, кроме того, литература, посвященная сэмплингу, исключительно обширна, так что невозможно проанализировать соответствующие достижения при ограниченном объеме этой статьи. Однако мы должны подчеркнуть, что сэмплинг часто является методом, дополнительным по отношению к гистограммам, поскольку статические гистограммы (и даже некоторые виды динамических гистограмм) обычно конструируются на основе образцов исходных данных [15, 26, 62].

Имеется также несколько специализированных методов, которые были предложены для решения некоторых специфических оценочных проблем, и в этих областях конкурируют с гистограммами. В их число входят методы оценки селективности запросов "select-join" [71] и пространственных запросов [8], использования обратной связи с запросом для обновления хранимой аппроксимирующей кривую/параметрической информации для улучшения оценки селективности [16], оценки селективности алфавитно-цифровых/строковых данных в одномерных [43, 45] и многомерных [41, 77] средах, определения квантилей (quantile) [6, 53, 54] и их динамической поддержки с априорной гарантией [29], приблизительных ответов на агрегатные запросы с соединениями [4], запросы "select-join" и в общей среде оперативной агрегации [33, 32, 51], вычисления частот высокочастотных элементов в потоке [52] и другие. Несмотря на то, что, по сравнению с этими методами, гистограммы не обеспечивают оптимальные решения, общая эффективность и широкая применимость гистограмм позволяет сохранять им конкурентноспособность и в этих случаях.

6. Будущее гистограмм

Несмотря на успех гистограмм, имеется несколько проблем, текущие решения которых могут быть существенно усовершенствованы, и несколько других проблем, которые остаются открытыми, и решение которых может существенно расширить область применимости гистограмм и/или повысить их эффективность. Различные проблемы обоих разновидностей обсуждаются в [35]; некоторые из них касаются конкретных характеристик гистограмм из существующей таксономии, а другие проявляются в несколько более общем контексте. В этом разделе мы фокусируемся на трех открытых проблемах, являющихся, по нашему мнению, наиболее актуальными и стоящими наиболее далеко от известных нам текущих исследовательских работ.

Методы гистограмм и кластеризация

Абстрагируясь от деталей проблемы аппроксимации на основе гистограмм, можно заметить ее поразительное сходство с традиционной проблемой кластеризации [73]: соединенное распределение данных разделяется на бакеты, содержащие схожие элементы. Сходство определяется на основе некоторой функции расстояния, в которой учитываются значения атрибутов данных и значение частоты, если он каким-то образом изменяется (например, не равняется единице для всех элементов данных). По существу, бакеты являются кластерами в традиционном смысле, и в каждом из них хранится очень краткая аппроксимация элементов, попавших в данный бакет. Несмотря на это сходство, методы, разработанные для решения этих двух проблем, вообще говоря, очень сильно различаются, причем причины многих из этих различий не задокументированы должным образом. Почему методы гистограмм, разработанные для оценки селективности, нельзя использовать для кластеризации и наоборот? С другой стороны, почему бы не рассматривать частоту в оценках селективности как еще одно измерение распределения данных и не считать эту проблему относящейся в области традиционной кластеризации? Как повлияло бы использование хранимых аппроксимаций, разработанных для одной проблемы, на другую проблему? И вообще, при наличии разнообразных методов, существующих для двух проблем, важно понимание достоинств и недостатков каждого из них, диапазона его применимости, а также относительные характеристики методов при их взаимном сравнении. Необходимо произвести

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

Распознавание и представление бакетов

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

Как мы узнаем, что параметры для элементов схожи, так что мы можем объединить их в группу и представить их в терминах параметров? Это типичный вопрос традиционного распознавания образов [73], где до применения каких бы то ни было методов кластеризации имеется начальная стадия, на которой из огромного числа возможностей выбираются подходящие измерения элементов. Имеется несколько методов выполнения такого выбора, успех которых изменяется в зависимости от ситуации.

Однако следует подчеркнуть, что, в принципе, эти параметры не обязательно должны присутствовать среди исходных измерений элементов данных, представленных в проблеме, а могут быть их производными. Например, в нескольких аппроксимациях на основе гистограмм, описанных выше, для частот близость определяется напрямую, а для атрибутов это не так, поскольку внимание уделяется их протяженности. (Напомним также об успехе варианта с площадью в качестве параметра источника, которая является произведением частоты на протяженность.) Предполагается что частоты в бакете являются константой, и для их аппроксимации требуется хранить меньший объем информации, чем для значений атрибутов, относительно которых предполагается следование линейному правилу (равные протяженности). Следовательно, традиционная аппроксимация на основе гистограмм при предположениях о равномерном распределении и равномерной протяженности подразумевает кластеризацию пространства частот и протяженностей. Однако, в принципе, этот подход наилучшим образом годится не для всех распределений данных.

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

Гистограммы и древовидные индексы

В нескольких работах признавался тот факт, что имеется тесная связь между приближенной статистикой, сохраняемой в базах данных, главным образом, гистограммами и индексами [7]. Если взглянуть на корень B+-дерева, то легко заметить, что появляющиеся в нем значения, по существу, разделяют атрибут, на котором построен индекс, на бакеты с соответствующими границами. Затем каждый бакет подразделяется на более мелкие бакеты узлами последующего уровня дерева. Можно представить, что рядом с каждым бакетом, специфицированным в узле, сохраняется соответствующая информация, так что узел преобразуется в гистограмму, а индекс целиком - в так называемую иерархическую гистограмму. Конечно, это может неблагоприятно повлиять на эффективность поиска в индексе, поскольку может уменьшить полустепень исхода узла (out-degree) и тем самым увеличить глубину дерева. Тем не менее, хотя эта идея работает против функциональности индекса, нельзя игнорировать ее достоинства, и этот подход даже внедрен в некоторых системах.

Мы полагаем, что иерархические гистограммы и вообще взаимодействие между аппроксимирующими структурами и индексами следует продолжать исследовать, поскольку, как показывает приводимый ниже анализ, несколько интересных проблем остаются неисследованными. Снова рассмотрим B+-дерево, узлы которого полностью заполнены. В этом случае корень дерева специфицирует разделение на бакеты домена атрибута, соответствующее гистограмме с одинаковой шириной, т.е. каждый бакет содержит примерно одинаковое число элементов. Аналогично, каждый узел дерева специфицирует разделение на бакеты с одинаковой шириной диапазона значений, к которым ведет этот узел.

Основной проблемой превращения B+-деревьев в гистограммы с одинаковой шириной является то, что эти гистограммы далеки от оптимальных при оценке селективности [67]. Гораздо эффективнее гистограммы классов v-optimal и maxdiff. Какие виды индексов следует применять, чтобы каждый узел представлял разделение на бакеты в соответствии с одним из этих правил? Ясно, что деревья были бы несбалансированными. Это сделало бы традиционный поиск в среднем менее эффективным. С другой стороны, другие виды поиска могли бы поддерживаться более эффективно. В частности, в системе, обеспечивающей приблизительные ответы на запросы, корень такого дерева обеспечивал бы более качественный ответ, чем корень соответствующего B+-дерева. Кроме того, система может перейти в поступательный режим, продвигаясь по дереву обычным образом и обеспечивая последовательность ответов с постоянным улучшением качества, в конце концов достигая листов и окончательного, точного ответа.

Возвращаясь к точным ответам на запросы, заметим, что обычно индексы строятся в предположении, что все значения в диапазонах значений одинаково важны. Поэтому важно иметь сбалансированное дерево. Однако часто бывает так, что разные значения обладают разной важностью и разной частотой в ожидаемой рабочей нагрузке [46]. Если эта частота запросов или некоторый другой подобный параметр используется в соединении с развитыми гистограммными правилами разделения на бакеты, то могут генерироваться некоторые очень интересные деревья, обеспечивающие намного лучшую среднюю эффективность поиска, чем у B+-деревьев.

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

7. Заключение

В мире баз данных гистограммы оказались очень успешными. Причина этого в том, что, среди нескольких существующих конкурирующих методов, они, по всей вероятности, представляют оптимальный подход, в котором балансируется компромисс между простотой, эффективностью и применимостью для аппроксимации/сжатия данных. Как кажется, основные проблемы в области гистограмм решены, но мы полагаем, что для некоторых их них имеются более совершенные решения. Более того, как говорилось в предыдущем разделе, имеется несколько незатронутых исследованиями фундаментальных проблем, для решения которых могут потребоваться существенные изменения в наших общих представлениях о гистограммах. Поскольку последние десять лет позволили углубить наше общее понимание гистограмм и расширить их применение в реальном мире, мы уверены, что следующие десять лет будут еще более впечатляющими.

8. Личная история

На нашу личную историю в связи гистограммами сильнейшим образом повлиял Ставрос Кристодолакис (Stavros Christodoulakis). Все началось во время "Query Optimization Workshop", который проходил во время конференции SIGMOD'89 в Портланде. Тогда Ставрос утверждал, что оптимизация очень больших запросов с соединениями лишена всякого смысла, поскольку ошибки оценок селективности станут очень велики уже после нескольких соединений. Руководствуясь собственным интересом к оптимизации больших запросов и желая доказать, что Ставрос не прав, мы начали сотрудничать с ним в решении проблемы распространения ошибок, и результаты этой работы полностью подтвердили опасения Ставроса [36]. В течение этой исследовательской работы Ставрос ввел нас в замечательный мир теории мажорирования, функций Шура (Schur) и других математических средств, на которых основывалась большая часть наших следующих работ. Дальнейшее сотрудничество с Кристодолакисом привело к определению "сериальных гистограмм" и осознанию их значимости [37], что явилось плацдармом для статьи на VLDB'93. По поводу всего этого свою искреннюю благодарность за выявление впечатляющего направления исследований, скрывавшего много сокровищей.

Вторым человеком, который существенно способствовал определению границ наших исследований в области гистограмм, является Виши Пусала (Vishy Poosala). Будучи аспирантом Висконсинского университете, Виши обратился к исходным результатам по "сериальным гистограммам", глубоко в них погрузился и распределил их во многих направлениях. Эта работа в конце концов привела нас к нескольким интересным результатам, которые сыграли важную роль в развитии успешного применения гистограмм. Спасибо Виши за долгую и плодотворную совместную работу как до, так и после его защиты диссертации.

Благодарности.

По поводу данной статьи мы хотели бы поблагодарить Миноса Гарофалакиса (Minos Garofalakis), Неоклиса Полизотиса (Neoklis Polyzotis) и снова Виши Пусала за несколько полезных советов и проверку того, что ошибка в аппроксимации истории гистограмм является небольшой.

Литература

[1]назад	Aboulnaga A., Alameldeen A., Naughton J.: Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. VLDB Conf. (2001) 591-600
[2]назад	Aboulnaga A., Chaudhuri S.: Self-tuning Histograms: Building Histograms Without Looking at Data. SIGMOD Conf. (1999) 181-192
[3]назад	Aboulnaga A., Naughton J.: Accurate Estimation of the Cost of Spatial Selections. ICDE 2000 123-134
[4]назад	Acharya S., Gibbons P., Poosala V., Ramaswamy S.: Join Synopses for Approximate Query Answering. SIGMOD Conf. (1998) 275-286
[5]назад	Acharya S., Poosala V., Ramaswamy S.: Selectivity Estimation in Spatial Databases. SIGMOD Conf. (1999) 13-24
[6]назад	Alsabti K., Ranka S., Singh V.: A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data. VLDB Conf. (1997) 346-355
[7]назад	Barbar_a D., et al.: The New Jersey Data Reduction Report. Data Engineering Bulletin 20:4 (1997) 3-45
[8]назад	Belussi A., Faloutsos C.: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB Conf. (1995) 299-310
[9]назад	Blakeley J., Kline N.: personal communication. (2003)
[10] назад	Blohsfeld B., Korus D., Seeger, B.: A Comparison of Selectivity Estimators for Range Queries on Metric Attributes. SIGMOD Conf. (1999) 239-250
[11]назад	Bruno N., Chaudhuri S., Gravano L.: STHoles: A Multidimensional Workload-Aware Histogram. SIGMOD Conf. (2001) 294-305
[12]назад	Bruno N., Chaudhuri S., Gravano L.: Exploiting Statistics on Query Expressions for Optimization SIGMOD Conf. (2002) 263-274
[13]назад	Buccafurri F., Rosaci D., Sacc_a D.: Improving Range Query Estimation on Histograms. ICDE (2002) 628-238
[14]назад	Chakrabarti K., Garofalakis M., Rastogi R., Shim K.: Approximate Query Processing Using Wavelets. VLDB Journal 10:2-3 (2001) 199-223
[15]назад	Chaudhuri S., Motwani R., Narasayya V.: Random Sampling for Histogram Construction: How Much is Enough? SIGMOD Conf. (1998) 436-447
[16]назад	Chen C., Roussopoulos N.: Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conf. (1994) 161-172
[17]назад	Choi Y.-J., Chung C.-W.: Selectivity Estimation for Spatio-Temporal Queries to Moving Objects. SIGMOD Conf. (2002) 440-451
[18]назад	De Boor C.: A Practical Guide to Splines. Springer (1994)
[19]назад	Deshpande A., Garofalakis M., Rastogi R.: Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data. SIGMOD Conf. (2001) 199-210
[20]назад	Donjerkovic D., Ramakrishnan R.: Probabilistic Optimization of Top N Queries. VLDB Conf. (1999) 411-422
[21]назад	Flickner M., et al.: Query by Image and Video Content: The QBIC System. IEEE Computer 28:9 (1995) 23-32
[22]назад	Freire J., Haritsa J., Ramanath M., Roy P., Simeon J.: StatiX: Making XML Count. SIGMOD Conf. (2002) 181-191
[23]назад	Furtado P., Madeira H.: Summary Grids: Building Accurate Multidimensional Histograms. DASFAA Conf. (1999) 187-194
[24]назад	Garofalakis M., Gibbons P.: Wavelet Synopses with Error Guarantees. SIGMOD Conf. (2002) 476-487
[25]назад	Getoor L., Taskar B., Koller D.: Selectivity Estimation Using Probabilistic Models. SIGMOD Conf. (2001) 461-472
[26]назад	Gibbons P., Matias Y., Poosala V.: Fast Incremental Maintenance of Approximate Histograms. VLDB Conf. (1997) 466-475
[27]назад	Gilbert A., Guha S., Indyk P., Kotidis Y., Muthukrishnan S., Strauss M.: Fast, Small-Space Algorithms for Approximate Histogram Maintenance. ACM STOC (2002) 389-398
[28]назад	Gilbert A., Kotidis Y., Muthukrishnan S., Strauss M.: Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. VLDB Conf. (2001) 79-88
[29]назад	Gilbert A., Kotidis Y., Muthukrishnan S., Strauss M.: How to Summarize the Universe: Dynamic Maintenance of Quantiles. VLDB Conf. (2002) 454-465
[30]назад	Guha S., Indyk P., Muthukrishnan S., Strauss M.: Histogramming Data Streams with Fast Per-Item Processing. ICALP Conf. (2002) 681-692
[31]назад	Gunopulos D., Kollios G., Tsotras V., Domeniconi C.: Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes. SIGMOD Conf. (2000) 463-474
[32]назад	Haas P., Hellerstein J.: Ripple Joins for Online Aggregation. SIGMOD Conf. (1999) 287-298
[33]назад	Hellerstein J., Haas P., Wang H.: Online Aggregation. SIGMOD Conf. (1997) 171-182
[34]назад	Ioannidis Y.: Universality of Serial Histograms. VLDB Conf. (1993) 256-267
[35]назад	Ioannidis Y.: Approximations in Database Systems. ICDT (2003) 16-30
[36]назад	Ioannidis Y., Christodoulakis S.: On the Propagation of Errors in the Size of Join Results. SIGMOD Conf. (1991) 268-277
[37]назад	Ioannidis Y., Christodoulakis S.: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM TODS 18:4 (1993) 709-748
[38]назад	Ioannidis Y., Poosala V.: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conf. (1995) 233-244
[39]назад	Ioannidis Y., Poosala V.: Histogram-Based Approximation of Set-Valued Query-Answers. VLDB Conf. (1999) 174-185
[40]назад	Jagadish H. V., Jin H., Ooi B. C., Tan K.-L.: Global Optimization of Histograms. SIGMOD Conf. (2001) 223-234
[41]назад	Jagadish H. V., Kapitskaia O., Ng R., Srivastava D.: Multi-Dimensional Substring Selectivity Estimation. VLDB Conf. (1999) 387-398
[42]назад	Jagadish H. V., Koudas N., Muthukrishnan S., Poosala V., Sevcik K., Suel T.: Optimal Histograms with Quality Guarantees. VLDB Conf. (1998) 275-286
[43]назад	Jagadish H. V., Ng R., Srivastava D.: Substring Selectivity Estimation. PODS Symposium (1999) 249-260
[44]назад	Koudas N., Muthukrishnan S., Srivastava D.: Optimal Histograms for Hierarchical Range Queries. PODS Symposium (2000) 196-204
[45]назад	Krishnan P., Vitter J., Iyer B.: Estimating Alphanumeric Selectivity in the Presence of Wildcards. SIGMOD Conf. (1996) 282-293
[46]назад	König A., Weikum G.: Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation. VLDB Conf. (1999) 423-434
[47]назад	Kooi R.: The Optimization of Queries in Relational Databases. PhD Thesis, Case Western Reserve University (1980)
[48]назад	Lee J.-H., Kim D.-H., Chung C.-W.: Multi-Dimensional Selectivity Estimation Using Compressed Histogram Information. SIGMOD Conf. (1999) 205-214
[49]назад	Lim L., Wang M., Padmanabhan S., Vitter J., Parr R.: XPathLearner: An On-Ling Self-Tuning Markov Histogram for XML Path Selectivity Estimation. VLDB Conf. (2002) 442-453
[50]назад	Lohman G.: personal communication. (2003)
[51]назад	Luo G., Ellmann C., Haas P., Naughton J.: A Scalable Hash Ripple Join Algorithm. SIGMOD Conf. (2002) 252-262
[52]назад	Manku G. S., Motwani R.: Approximate Frequency Counts over Data Streams. VLDB Conf. (2002) 346-357
[53]назад	Manku G. S., Rajagopalan S., Lindsay B.: Approximate Medians and Other Quantiles in One Pass and with Limited Memory. SIGMOD Conf. (1998) 426-435
[54]назад	Manku G. S., Rajagopalan S., Lindsay B.: Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. SIGMOD Conf. (1999) 251-262
[55]назад	Marshall A., Olkin L.: Inequalities: Theory of Majorization and its Applications. Academic Press (1986)
[56]назад	Matias Y., Vitter J., Wang M.: Wavelet-Based Histograms for Selectivity Estimation. SIGMOD Conf. (1998) 448-459
[57]назад	Matias Y., Vitter J., Wang M.: Dynamic Maintenance of Wavelet-Based Histograms. VLDB Conf. (2000) 101-110
[58]назад	Muralikrishna M., DeWitt D.: Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries. SIGMOD Conf. (1988) 28-36
[59]назад	Muthukrishnan S., Poosala V., Suel T.: On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications. ICDT (1999) 236-256
[60]назад	Papadopoulos A., Manolopoulos Y.: Structure-Based Similarity Search with Graph Histograms. DEXAWorkshop (1999) 174-179
[61]назад	Pass G., Zabih R.: Comparing Images Using Joint Histograms. Multimedia Systems 7 (1999) 234-240
[62]назад	Piatetsky-Shapiro G., Connell C.: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conf. (1984) 256-276
[63]назад	Polyzotis N., Garofalakis M.: Statistical Synopses for Graph-Structured XML Databases. SIGMOD Conf. (2002) 358-369
[64]назад	Polyzotis N., Garofalakis M.: Structure and Value Synopses for XML Data Graphs. VLDB Conf. (2002) 466-477
[65]назад	Poosala V., Ioannidis Y.: Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing. VLDB Conf. (1996) 448-459
[66]назад	Poosala V., Ioannidis Y.: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB Conf. (1997) 486-495
[67]назад	Poosala V., Ioannidis Y., Haas P., Shekita E.: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. (1996) 294-305
[68]назад	Sitzmann I., Stuckey P.: Improving Temporal Joins Using Histograms. DEXA Conf. (2000) 488-498
[69]назад	Stigler S.: The History of Statistics: The Measurement of Uncertainty before 1900. Harvard University Press (1986)
[70]назад	Stillger M., Lohman G., Markl V., Kandil M.: LEO - DB2's LEarning Optimizer. VLDB Conf. (2001) 19-28
[71]назад	Sun W., Ling Y., Rishe N., Deng Y.: An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conf. (1993) 79-88
[72]назад	Thaper N., Guha S., Indyk P., Koudas N.: Dynamic Multidimensional Histograms. SIGMOD Conf. (2002) 428-439
[73]назад	Theodoridis, S., Koutroumbas K.: Pattern Recognition. Academic Press, 2nd edition (2003)
[74]назад	Tufte E.: The Visual Display of Quantitative Information. Graphics Press (1983)
[75]назад	Vitter J., Wang M.: Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets. SIGMOD Conf. (1999) 193-204
[76]назад	Vitter J., Wang M., Iyer B.: Data Cube Approximation and Histograms via Wavelets. CIKM Conf. (1998) 96-104
[77]назад	Wang M., Vitter J., Iyer B.: Selectivity Estimation in the Presence of Alphanumeric Correlations. ICDE (1997) 169-180
[78]назад	Witkowski A.: personal communication. (2003)
[79]назад	Wu Y., Patel J., Jagadish H. V.: Using Histograms to Estimate Answer Sizes for XML Queries. Information Systems 28:1-2 (2003) 33-59