#sql #алгоритм #postgresql #математика #postgis
В таблице 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х мерные проекции и пытаться индексировать на них.
Ответы
Ответ 1
Есть методики понижения размерности, когда из N измерений делается два или три. Например: Independent Component Analysis (ICA) Principal Component Analysis (PCA) Nonnegative Matrix Factorization (NMF) Известны и многие другие способы подойти к проблеме излишнего числа измерений. В том числе можно посмотреть на алгоритмы кластеризации. Не обязательно на ваших данных любой из этих алгоритмов будет работать хорошо, но какой-то может дать приемлемые результаты. Другое дело что вы далеко не уедете, считая ваши данные непрозрачными. Вам хорошо бы понять, какие координаты что означают. Наверняка ж эти векторы не из случайных чисел. Скорее всего вы берете их из предпоследнего слоя нейронной сети. Значит можно для какой-то известной выборки, которая кардинально отличается по какому-то фактору, можно выяснить какой нейрон соответствует этому фактору. И вот у вас уже одна из координат для трехмерного вектора, по которому можно быстро искать.Ответ 2
Можно делить на кубики не равномерно а адаптивно, и хранить не все кубики а только те что содержат элементы. Например если в кубик входит несколько элементов, например больше 15, то тогда дробим его на части. Получается массив кубиков разного размера, либо дерево кубиков. Тогда алгоритм решения будет таким. Ищем самый маленький куб в который входит элемент, эта операция где-то между константой по сложности и логарифмической сложностью, если вектора будет концентрироваться в одной точке. И уже дальше проверяем только элементы из этого кубика и соседних (на случай если вектор находится рядом с границей кубика). Обновлено: Но тут возникает проблема с соседними квадратами.... Дело в том что в плоскости соседей - 8, в 3-х мерном пространстве 26... а в 128-ми мерном, их будет очень много. В этой ситуации можно сделать так, рассчитать минимальное расстояние до края, если из найденных расстояний в этом же кубе расстояние меньше чем до ближайшего края то вектор найден. Если же край ближе, тогда уже ищем по соседям или полным перебором.Ответ 3
Это, скорее, комментарий, а не ответ, но в комментарий он не поместился. Тут я вижу два направления - куда копать. Первое - "buckets" из PostgreSQL. Не могу сказать точно, насколько они сюда подходят, - я сам ими не пользовался, только читал. Второе - старые добрые ячейки для нахождения точки из набора, ближайшей к данной точке. Делим Ваш 128-мерный мир на кубики. Размер кубика будет зависеть от диапазонов координат, кубики могут быть параллелепипедами. Все кубики пронумерованы - номер кубика может быть вычислен из его индексов по всем 128-и осям (индексы по осям находятся простым делением). Все точки заранее распределяем по кубикам. Находим, в какой кубик попадает данная точка. Многое зависит от равномерности распределения точек в пространстве. Вычислять [квадрат] расстояния можно только для точек в том же кубике или в в нем и кубиках его окружающих (их, правда, будет три в 128-й степени). Update Мне точно не интересны точки, отдаленные друг от друга более чем на 1.0. Это отличное условие для предварительной выборки: WHERE ABS(v1[1]-v2[1]) < 1 AND ABS(v1[2]-v2[2]) < 1 AND ... AND ABS(v1[128]-v2[128]) < 1
Комментариев нет:
Отправить комментарий