13 521
правка
Изменения
м
Обычное KДля индексации многомерных данных придумано очень много разных структур и алгоритмов. Большинство из них, правда, осталось на теоретическом уровне статей и диссертаций :) в реальности обычно используются самые простые вариации. В целом, все многомерные индексы делятся на два класса:* Производные от R-D дерева. R-дерево - наиболее известная и используемая в реальности индексная структура (от KR -Dimensionalот Region) , прямое обобщение B-деревьев на многомерный случай. Узлы индекса - "гиперпрямоугольники" многомерного пространства, которые могут содержать либо точки, либо дочерние узлы. R-дерево представляет собой вид BSPэффективно работает для минимальных размерностей (2-3) и поэтому широко используется для хранения пространственных данных, например, положений объектов на картах местности. При увеличении размерности, однако, возникает проблема перекрытия узлов и индекс перестаёт давать ускорение, т.к. при поиске оказывается нужно заглянуть в почти все узлы. Соответственно, большинство производных от R-дерева структур ставят своей целью именно борьбу с перекрытиями узлов.* BSP-деревья и их обобщения (BSP = Binary Space Partitioning, ). Каждый узел представляет собой разбиение пространства на две части), в котором все разбиения осуществляются гиперплоскостямитаким образом, перпендикулярными одной из осей координат. Каждый узел K-D дерева характеризуется номером координаты и пороговым значением. Если значение выбранной координаты в точке меньше или равно этого порогового значения, точка относится к левому подпространству, а если больше — к правомучасти пространства никогда не пересекаются.
→K-D-N дерево
В простейшей реализации алгоритма поиска повторов все сгенерированные вектора спектральных координат сравниваются друг с другом попарно, что сильно ухудшает производительность. Порядок сложности такого алгоритма — O(N²). Чтобы его ускорить, нужно применять индексные структуры, позволяющие уменьшить сложность поиска.
Существуют индексы, разрабатываемые специально для использования в СУБД - обычно от таких индексов требуется ориентация на дисковое хранение и обновляемость без значительной потери эффективности. Существуют и более простые структуры, предназначенные для использования в памяти и не имеющие возможности обновления. На самом деле, из реально широко используемых обновляемых многомерных индексов можно упомянуть только R-дерево. Обычное K-D (от K-Dimensional) дерево представляет собой вид BSP-дерева, в котором все разбиения осуществляются гиперплоскостями, перпендикулярными одной из осей координат. Каждый узел K-D дерева характеризуется номером координаты и пороговым значением. Если значение выбранной координаты в точке меньше или равно этого порогового значения, точка относится к левому подпространству, а если больше — к правому. Выбор разделяющих плоскостей в простейшей и наиболее часто используемой реализации K-D дерева делается просто — выбирается медианное значение нужной координаты по всей выборке индексируемых точек. Таким образом строится сбалансированное КK-Д D дерево. Выбор измерения для разбиения пространства на каждом шаге в простейшем случае производится по кругу, начиная с первого измерения - такой подход даёт наибольшее "равноправие" измерений.
