У меня есть большая база данных (16 миллионов строк), содержащая перцептивные хеши изображений.
Я хотел бы иметь возможность искать строки по расстоянию Хэмминга в разумные сроки.
В настоящее время, насколько я правильно понимаю проблему, я думаю, что лучшим вариантом здесь была бы пользовательская реализация SP-GiST, которая реализует BK-Tree , но это кажется большой работой, и я все еще не совсем уверен в практической детали правильной реализации пользовательского индекса. Расчет расстояния Хэмминга достаточно податлив, и я все же знаю C.
В принципе, то , что является подходящим подходом здесь? Мне нужно иметь возможность запрашивать совпадения в пределах определенного расстояния редактирования хэша. Насколько я понимаю, расстояние Левенштейна со строками равной длины - это функциональное расстояние Хемминга, так что есть, по крайней мере, некоторая существующая поддержка того, что я хочу, хотя нет четкого способа создать из него индекс (помните, значение, которое я запрашиваю для изменения. Я не могу предварительно вычислить расстояние от фиксированного значения, так как это было бы полезно только для этого одного значения).
Хеши в настоящее время хранятся в виде строки из 64 символов, содержащей двоичную ASCII-кодировку хеша (например, «10010101 ...»), но я могу достаточно легко преобразовать их в int64. Реальная проблема в том, что мне нужно уметь делать запросы относительно быстро.
Кажется, что можно достичь чего-то в соответствии с тем, что я хочу с помощью pg_trgm, но мне немного неясно, как работает механизм сопоставления триграмм (в частности, что на самом деле представляет метрика сходства, которую он возвращает ? вроде как расстояние редактирования).
Производительность вставки не критична (вычислять хэши для каждой строки очень дорого в вычислительном отношении), поэтому я в первую очередь забочусь о поиске.
источник
Ответы:
Что ж, я потратил некоторое время на то, чтобы написать собственное расширение C для postgres, и занялся написанием оболочки базы данных Cython, которая поддерживает структуру BK-дерева в памяти.
По сути, он поддерживает в памяти копию значений phash из базы данных, и все обновления базы данных воспроизводятся в BK-дереве.
Это все на github здесь . Он также имеет множество юнит-тестов.
Запрос по набору данных из 10 миллионов значений хеш-функции для элементов с расстоянием 4 приводит к касанию ~ 0,25% -0,5% значений в дереве и занимает ~ 100 мс.
источник
МОРА ОТВЕТЫ!
Хорошо, я наконец-то нашел время для написания собственного индексационного расширения PostgreSQL. Я использовал интерфейс SP-GiST .
Это было довольно сложно, в основном из-за того, что Posgres большой .
В любом случае, как обычно, это на github здесь .
Что касается производительности, то в настоящее время она примерно в 2-3 раза медленнее, чем реализация в памяти, как в моем другом ответе на этот вопрос, но это гораздо удобнее в использовании, и я с удовольствием воспользуюсь этим снижением производительности (реально, это ~ 50 мс / запрос - 150 мс / запрос, что все еще довольно мало).
источник