Классика баз данных - статьи
Правила многомерных разделений
Многомерные гистограммы были впервые введены Мураликришной и ДеВиттом (Muralikrishna и DeWitt) [], которые, по существу, описали двухмерные гистограммы с одинаковой глубиной. Пространство разделялось таким же образом, как это делается в Grid-файлах, т.е. путем рекурсивного разрезания всего пространства на два подпространства, каждый раз с использованием в качестве границы значения одного измерения. Измерение и значение выбирались способом, предписанным в начале этого процесса []. Бакеты были неперекрывающимися (многомерный вариант сериального класса разделения) в пространстве многомерных значений (многомерный вариант значения как параметра разделения).
Только несколько лет спустя были предложены некоторые новые правила разделения [], которые опирались на универсализм таксономии гистограмм []. Наиболее эффективным семейством таких правил было MHIST-2, которое начинает со всего распределения данных, размещенного в одном бакете, и на каждом шаге расщепляет пространство, занимаемое одним из сформированных ранее бакетов, на два подпространства, пока не исчерпается бюджет бакетов. Расщепление производится в том бакете и по тому измерению, которые характеризуются как наиболее "критические", т.е. частное распределение (marginal distribution) которых больше всего нуждается в разделении. Расщепление основывается на используемых (одномерном) ограничении разделения и параметре источника. В сочетании с наиболее эффективными ограничениями разделения (т.е. с v-optimal или maxdiff с частотой или площадью) MHIST-2 представляет значительное усовершенствование исходных многомерных гистограмм с одинаковой глубиной.
После появления MHIST было предложено много интересных правил разбиения. Одним из них является семейство правил GENHIST [], которое изначально было предложено в контексте многомерных вещественных данных, но его применимость оказалась более широкой. Основная характеристика GENHIST состоит в том, что оно допускает перекрытие бакетов в пространстве многомерных значений: алгоритм начинает свою работу с равномерного сеточного разделения (grid partitioning) пространства, а затем итеративно укрупняет бакеты, содержащие большое число элементов данных.
