Поиск по минимальному эвклидовому расстоянию между заданным вектором и векторами в БД

В таблице PostgreSQL в поле типа double[] хранятся векторы высокой размерности (128 координат если быть точным).
create table tab ( id integer, name character varying(200) vector double precision[] )
По заданному вектору нужно вернуть из БД одну запись с минимальным эвклидовым расстоянием между этим вектором и вектором в записи таблицы.
Имеется функция которая вычисляет эвклидово расстояние двух векторов по всем известной формуле SQRT((v1[1]-v2[1])^2+(v1[2]-v2[2])^2+....+(v1[128]-v2[128])^2)
CREATE OR REPLACE FUNCTION public.euclidian( arr1 double precision[], arr2 double precision[]) RETURNS double precision AS $BODY$ select sqrt(SUM(tab.v)) as euclidian from (SELECT UNNEST(vec_sub(arr1,arr2)) as v) as tab; $BODY$ LANGUAGE sql IMMUTABLE STRICT
Вспомогательная функция:
CREATE OR REPLACE FUNCTION public.vec_sub( arr1 double precision[], arr2 double precision[]) RETURNS double precision[] AS $BODY$ SELECT array_agg(result) FROM (SELECT (tuple.val1 - tuple.val2)*(tuple.val1 - tuple.val2) AS result FROM (SELECT UNNEST($1) AS val1 ,UNNEST($2) AS val2 ,generate_subscripts($1, 1) AS ix) tuple ORDER BY ix) inn; $BODY$ LANGUAGE sql IMMUTABLE STRICT
Запрос :
select tab.id as tabid, tab.name as tabname, euclidian(target_vector,tab.vector) as eucl from tab order by eulc ASC limit 1
Пока всё отлично работает. Но нетрудно заметить, что запрос может быть выполнен не иначе как полным перебором всех записей в таблице tab. До определенного момента это всех устраивало, но сейчас база данных подрастает и встает вопрос что полный перебор не очень хорош мягко говоря. Сейчас в базе несколько тысяч записей и явных проблем с производительностью пока нет, но десятки и сотни тысяч записей не за горами.
Вопрос - как можно изловчиться и обеспечить индексный поиск в таблице tab при выполнении запроса? Чтобы хотя бы 90% ненужных записей отбрасывалось по индексу, а в оставшихся 10% уже допустимо полным перебором пройти.
P.S. одно из текущих направлений поиска решения: расширение PostGIS позволяет вести поиск и сортировку по расстоянию (ST_3DDistance), фильтр по удаленности (ST_3DWithin) и пр. в 3-х мерном пространстве - делается это быстро по индексам. Может быть как-то кто-то это абстрагировал на случай N-мерного пространства?
P.S.2. данные метеорологических наблюдений:
сделал запрос select max(val), min(val) from (select unnest(vector) as val from tab) as tab1 - 0.485470712185 -0.41735497117 - я точно не знаю, думаю значения координат в теории не превышают 1.0 по модулю при этом векторы не нормализованы, расстояние от (0,0,...0) лежит в пределах от 1.2 до 1.6.
P.S.3. Подобную задачу не первый раз решаю - предыдущий раз это было связано с поиском ближайшей точки в облаке точек (3D), но там у меня было все локально в памяти (база данных iBoxDB), там даже и не рыпался от полного перебора уйти... а тут вся мощь сервера postgresql - из принципа хочется решить).
P.S.4. Исходя из данных наблюдений, максимальное расстояние между точками (на основании имеющейся статистики) составляет примерно 3.2 - расширим на всякий случай до 5, ну или до 10. Мне точно не интересны точки, отдаленные друг от друга более чем на 1.0. Выделим из 128-мерного пространства несколько (сколько не жалко, скажем 10,20) трехмерных проекций - наборов координат (v1,v2,v3), (v4,v5,v6), и т.д. Очевидно, если в одной из трехмерных проекций расстояние превысило лимит (1.0) - то меньшим на полном наборе координат оно точно уже не станет. Далее пытаемся применить то что есть в PostGIS - индексируем каждую их трехмерных проекций векторов и затем при поиске ставим фильтры с помощью ST_3DWithin < 1.0 (количество фильтров будет равно количеству выделенных трехмерных проекций). Стоит попробовать в новогоднюю ночь :-) Очень бы хотелось компетентный комментарий гуру по PostGIS - случится ли чудо в новогоднюю ночь, или можно спокойно веселиться? :-)
P.S.5. В сторону buckets предлагаю больше не копать - во первых их ну ооочень много получится, как не раскидывай - даже если строить на проекции а не на полной размерности, скажем взять первых 64 координаты и раскидать по букетам (<0,>=0) - получится 18446744073709551616 возможных букетов - куда тут... Во вторых, есть проблема границ букетов - точки могут находиться на минимальном расстоянии но попасть в соседние букеты, это нада учитывать в запросах, для этого нужно держать диаграмму соседей для каждого букета... если же применять простейшее разбиение (<0,>=0) - оно в принципе теряет всякий смысл, потому что для одной оси граница только одна и нужно все равно искать и там и там... а если разбивать каждую ось на 4 диапазона - количество букетов уверенно уйдёт в бесконечность... В третьих, не хотелось бы создавать велосипед с помощью напильника - если ГИС-системы решают задачу на трехмерных координатах - либо абстрагировать эти механизмы на большие размерности, либо выделять 3х мерные проекции и пытаться индексировать на них.

Ответ

Есть методики понижения размерности, когда из N измерений делается два или три. Например:
Independent Component Analysis (ICA) Principal Component Analysis (PCA) Nonnegative Matrix Factorization (NMF)
Известны и многие другие способы подойти к проблеме излишнего числа измерений. В том числе можно посмотреть на алгоритмы кластеризации
Не обязательно на ваших данных любой из этих алгоритмов будет работать хорошо, но какой-то может дать приемлемые результаты.
Другое дело что вы далеко не уедете, считая ваши данные непрозрачными. Вам хорошо бы понять, какие координаты что означают. Наверняка ж эти векторы не из случайных чисел. Скорее всего вы берете их из предпоследнего слоя нейронной сети. Значит можно для какой-то известной выборки, которая кардинально отличается по какому-то фактору, можно выяснить какой нейрон соответствует этому фактору. И вот у вас уже одна из координат для трехмерного вектора, по которому можно быстро искать.