Классика баз данных - статьи
Конкуренты гистограмм
Основным методом, конкурирующим с гистограммами в последние десять лет являются вейвлеты, которые играют очень важную роль в области сжатия изображений, а в области баз данных начали применяться в конце 90-х [, ]. Вейвлеты широко используются для обеспечения приблизительных ответов на запросы разных типов и/или в различных средах: многомерные агрегатные запросы (range-sum queries) в средах OLAP [, ], агрегатные и не агрегатные запросы с вычислениями непосредственно над хранимыми коэффициентами вейвлетов [] и ограничительные или агрегатные запросы над потоками []. Как и в случае гистограмм, предпринимаются усилия по разработке методов, основанных на вейвлетах, которые обеспечивают приблизительные ответы на запросы с гарантированным уровнем ошибок [], а также методов динамического конструирования и поддержки наиболее важных коэффециентов вейвлетов [].
Сэмплинг не является прямым конкурентом гистограмм, поскольку это, главным образом, метод времени выполнения (runtime technique), и, кроме того, литература, посвященная сэмплингу, исключительно обширна, так что невозможно проанализировать соответствующие достижения при ограниченном объеме этой статьи. Однако мы должны подчеркнуть, что сэмплинг часто является методом, дополнительным по отношению к гистограммам, поскольку статические гистограммы (и даже некоторые виды динамических гистограмм) обычно конструируются на основе образцов исходных данных [, , ].
Имеется также несколько специализированных методов, которые были предложены для решения некоторых специфических оценочных проблем, и в этих областях конкурируют с гистограммами. В их число входят методы оценки селективности запросов "select-join" [] и пространственных запросов [], использования обратной связи с запросом для обновления хранимой аппроксимирующей кривую/параметрической информации для улучшения оценки селективности [], оценки селективности алфавитно-цифровых/строковых данных в одномерных [, ] и многомерных [, ] средах, определения квантилей (quantile) [, , ] и их динамической поддержки с априорной гарантией [], приблизительных ответов на агрегатные запросы с соединениями [], запросы "select-join" и в общей среде оперативной агрегации [, , ], вычисления частот высокочастотных элементов в потоке [] и другие. Несмотря на то, что, по сравнению с этими методами, гистограммы не обеспечивают оптимальные решения, общая эффективность и широкая применимость гистограмм позволяет сохранять им конкурентноспособность и в этих случаях.
