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