Изменения

Первая проблема — природа коэффициентов разложения. Их Они распределены весьма плотно по сравнению с типичным размером окрестности поиска, а распределение похоже на нормальное, и что ещё хуже, первые коэффициенты сильно больше последних по модулю. Сильно — это примерно на 1-2 порядка. Причины две — во-первых, в реальных данных низкочастотные гармоники всегда оказываются больше, во-вторых, в нашем случае высокочастотные гармоники приглушены нами же — исходный вектор длины K => разница между двумя соседними значениями в нём по модулю раскладываемом векторе значений не больше 1, если сетка полная (размер сетки = A), и не больше отношения длины окна A к размеру сетки A/KL, если она меньше A, так как разница между двумя соседними значениями в профиле последовательности равна либо 0, либо 1, либо −1. Следовательно, максимум i-го коэффициента разложения равен примерно (K+1-i)*A/KL. И всё это — распределено околонормальнооколо-нормально (чему, видимо, тоже есть обоснование — там же везде суммы «случайных» значений, а закон больших чисел никто не отменял).  Таким образом, разбиение пространства на какие-то области (построение индекса) уже становится проблемой — «полезных» измерений с большим относительно размера окрестности поиска диапазоном мало (3-5), бОльшая часть спектральных векторов распределена в центре всей области, центр маленький. То есть, при поиске приходится просматривать довольно много лишних векторов.

Кроме того, с очевидной оптимизацией линейный поиск становится ещё проще. При попарном сравнении всех векторов не нужно делать их сравнивать полностью! Их достаточно сравнивать с искомой окрестностью последовательно от первой координаты к последней K-ой. Учитывая природу коэффициентов разложения — это примерно соответствует порядку убывания абсолютных значений коэффициентов, а значит, в среднем и разности.

== K-D-N дерево Индексные структуры ==

* Производные от R-дерева. R-дерево - дерево — наиболее известная и используемая в реальности индексная структура (R - R — от Region), прямое обобщение B-деревьев на многомерный случай. Узлы индекса - "гиперпрямоугольники" индекса — «гиперпрямоугольники» многомерного пространства, которые могут содержать либо точки, либо дочерние узлы. R-дерево эффективно работает для минимальных размерностей (2-3) и поэтому широко используется для хранения пространственных данных, например, положений объектов на картах местности. При увеличении размерности, однако, возникает проблема перекрытия узлов и индекс перестаёт давать ускорение, т.к. так как при поиске оказывается нужно заглянуть в почти все узлы. Соответственно, большинство производных от R-дерева структур ставят своей целью именно борьбу с перекрытиями узлов.

Существуют индексы, разрабатываемые специально для использования в СУБД - СУБД — обычно от таких индексов требуется ориентация на дисковое хранение и обновляемость без значительной потери эффективности. Существуют и более простые структуры, предназначенные для использования в памяти и не имеющие возможности обновления. На самом деле, из реально широко используемых обновляемых многомерных индексов можно упомянуть только R-дерево. Существует два основных применения индексов для поиска:* Поиск ближайшего соседа (точки, наиболее близкой к заданной) или нескольких ближайших соседей. Здесь наиболее эффективны производные R-дерева, так как их узлы содержат границы областей, для каждого узла можно вычислить максимально возможное расстояние от искомого элемента, и соответственно, узлы можно просматривать сразу в нужном порядке.* Поиск по заданной области, требуемый как раз в нашем случае. В нашем случае не требуется ни внешнее хранение, ни обновляемость индекса (с ней у R-деревьев получше), поэтому более эффективными оказываются разделяющие деревья. === K-D дерево ===

Выбор разделяющих плоскостей в простейшей и наиболее часто используемой реализации K-D дерева делается просто — выбирается медианное значение нужной координаты по всей выборке индексируемых точек. Таким образом строится сбалансированное K-D дерево. Выбор измерения для разбиения пространства на каждом шаге в простейшем случае производится по кругу, начиная с первого измерения - измерения — такой подход даёт наибольшее "равноправие" «равноправие» измерений. == K-D-N дерево == K-D-N дерево:* Содержит уровней не больше, чем число измерений.* Нелистовые узлы содержат полное разбиение набора данных на диапазоны по одному из измерений, плюс вычисленные на этапе построения дерева минимальное и максимальное значение выбранного измерения у всех попавших в узел элементов. Размеры всех диапазонов одинаковы и равны половине размера ожидаемой окрестности, по которой будет производиться поиск. Больше хуже — массив данных очень плотный, и разделение пространства становится неэффективным. Меньше тоже хуже — сильно возрастает количество узлов дерева, которые нужно просматривать при поиске.* Если полный диапазон по какому-то измерению меньше, чем 1.5 * размер ожидаемой при запросе окрестности поиска, разбиение по этому измерению не производится, потому что оно всё равно будет неэффективно — при поиске почти наверняка придётся заглядывать во все дочерние узлы. Почему 1.5? Потому что это 3*ε, если ищем по окрестности (c-ε ≤ x ≤ c+ε). В этом случае пространство разделится на 3 «полосы» каждая размером по ε, запрашиваемый центр окрестности почти наверняка попадёт в центральную из этих полос (помним, что распределение у нас почти нормальное), соответственно, искомые элементы почти наверняка смогут оказаться в любой из трёх полос.* Листовые узлы содержат наборы элементов. Технически — списки индексов элементов в изначальном массиве данных. Сами элементы хранить смысла нет, так как нам всё равно нужны индексы, чтобы сопоставлять элементам положения в ДНК-последовательности.* Дополнительно создаются и хранятся вариационные ряды (списки индексов элементов), упорядоченные по каждой координате.* При поиске просто спускаемся по дереву, просматривая узлы, в которых могут содержаться подходящие элементы, и всё время запоминаем максимальное и минимальное значение по каждому измерению. Так как индексируемый набор данных известен полностью, запоминаются они в виде номера элемента в вариационном ряде — это позволяет избежать лишних операций с плавающей точкой.* После поиска нужно произвести окончательную фильтрацию неточного найденного набора элементов. Фильтрация по каждому измерению производится одним из двух способов, оптимальный из которых выбирается сравнением размера фильтруемого набора с количеством элементов, которые придётся отсечь на шаге 2:** Либо простым сравнением значения каждого элемента с искомой окрестностью — эффективно, если фильтруемый набор мал.** Либо отсечением кусков вариационного ряда по ассоциативному массиву. Для этого двоичным поиском находится положение минимального и максимального значения измерения искомой окрестности (c-ε, c+ε) в вариационном ряде по нужной координате, а потом участки вариационного ряда от «известного» до «найденного» максимального/минимального значения удаляются из результата. Под «известным» диапазоном понимается найденный на этапе обхода дерева. Технически — во временный массив по номерам элементов из этих участков вариационного ряда сохраняется «1», а фильтруемый набор одним проходом фильтруется с помощью проверки элементов временного массива. На самом деле, при многократном поиске временный массив можно не обнулять, а вместо «1» можно использовать увеличиваемый при каждом следующем поиска счётчик. Эта стратегия эффективна, если фильтруемый набор больше, чем сумма размеров удаляемых участков. Обычно это случается, либо если какое-то измерение почти ничего не фильтрует (то есть, если полный диапазон значений по этому измерению сопоставим с размером окрестности поиска), либо если просто найдено очень много элементов.* С помощью этих мер достигается эффективность индекса в ситуации, когда пространственный размер массива данных относительно маленький, значимых измерений относительно немного, но при этом нет ограничения на полное число измерений. == Дальнейшие изыскания == Новая идея, но это будет что-то типа гибрида KD- и M-дерева (K-D-M-дерево? :)). Т.е. юзать то же самое кд-дерево, но очень близкие элементы группировать в гиперкубики и индексировать их центры вместо самих элементов. Можно даже тотально перейти в целые числа.