Классика баз данных - статьи
Во многих наиболее удачных подходах
Во многих наиболее удачных подходах авторы старались избежать группирования в бакет чрезмерно различные значения параметра источника.
Следуя [], мы используем p(s,u) для обозначения сериального класса гистограмм с ограничением разделения p, параметром разделения s и параметром источника u.
Алгоритм конструирования: Это алгоритм, который по заданному правилу разделения конструирует гистограммы, соответствующие этому правилу. Часто для одного класса гистограмм существует несколько алгоритмов конструирования с разной эффективностью.
Аппроксимация значений: В этом аспекте фиксируется то, как внутри бакета аппроксимируются значения атрибута, что не зависит от правила разделения гистограммы. Наиболее распространенными альтернативами являются предположение о непрерывности значений (continuous value assumption) и предположение о равномерности протяженностей (uniform spread assumption); в обоих случаях предполагается, что значения равномерно размещаются в диапазоне, покрываемом бакетом, но в первом случае игнорируется число этих значений, а во втором это число регистрируется внутри бакета.
Аппроксимация частоты: В этом аспекте фиксируется то, как внутри бакета аппроксимируются частоты. Доминирующий подход опирается на предположение о равномерности частот (uniform distribution assumption), в котором предполагается, что частоты всех элементов в бакете одни и те же и равны среднему значению реальных частот.
Гарантии ошибок: Имеются верхние границы ошибок оценок, производимых гистограммой, обеспечиваемые на основе информации, которую поддерживает гистограмма.
Многомерная гистограмма на множестве атрибутов конструируется путем разделения соединенного распределения данных этих атрибутов. У таких гистограмм имеются точно такие же характеристики, как и у одномерных гистограмм, за исключением того, что требуется более сложное разделения, и оно не всегда так отчетливо раскладывается в четыре других характеристики, как раньше, например, в этом случае нет реального параметра разделения, поскольку в многомерном пространстве не может быть упорядоченности [].
