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