13 521
правка
Изменения
м
→K-D-N дерево
* Листовые узлы содержат наборы элементов. Технически — списки индексов элементов в изначальном массиве данных. Сами элементы хранить смысла нет, так как нам всё равно нужны индексы, чтобы сопоставлять элементам положения в ДНК-последовательности.
* Дополнительно создаются и хранятся вариационные ряды (списки индексов элементов), упорядоченные по каждой координате.
* При поиске просто спускаемся по дереву, просматривая узлы, в которых могут содержаться подходящие элементы, и всё время запоминаем максимальное и минимальное значение по каждому измерению. Так как индексируемый набор данных известен полностью, запоминаются они в виде номера элемента в вариационном рядеряде — это позволяет избежать лишних операций с плавающей точкой.
* После поиска нужно произвести окончательную фильтрацию данных. Фильтрация по каждому измерению производится одним из двух способов:
*# Простым сравнением значения каждого элемента с искомой окрестностью — эффективно, если фильтруемый набор мал.
*# Двоичным поиском минимального и максимального значения измерения искомой окрестности в соответствующем вариационном ряде и отсечением участков от «известного» минимального/максимального, сохранённого на этапе обхода дерева до найденного. Эта стратегия эффективна в двух случаях — во-первых, если фильтруемый набор достаточно велик, и во-вторых, если какое-то измерение почти ничего не фильтрует — то есть, если полный диапазон значений по этому измерению сопоставим с размером окрестности поиска.
* С помощью этих мер достигается эффективность индекса в ситуации, когда пространственный размер массива данных относительно маленький, значимых измерений относительно немного, но при этом нет ограничения на полное число измерений.