Изменения

Линейный поиск очень прост по сравнению с поиском по индексу — сложность одного шага поиска по индексу сама по себе гораздо больше сложности одного шага «тупого» поиска, так как, скорее всего, включает ветвления, переходы по дереву, запоминание списка найденных элементов и тому подобные операции. Поэтому, даже выигрывая в числе шагов, мы получим меньшее ускорение, чем хотели бы.

То есть, большая часть неподходящих нам векторов отсекается вообще по 1-ой координате. Относительно мало — по второй, ещё меньше — по третьей, и т. п. В реальности получается, что по коэффициентам дальше 6-го не отсекается почти ничего, а дальше 9-го — совсем ничего. В то же время, для полной проверки ''подходящего'' вектора нужно сделать в точности K сравнений и не меньше.

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

* С помощью этих мер достигается эффективность индекса в ситуации, когда пространственный размер массива данных относительно маленький, значимых измерений относительно немного, но при этом нет ограничения на полное число измерений.